108142024-04-15 14:26:40AblablablaAutó-tortúracpp17Runtime error 24/100711ms13136 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF = 1e16;

int main(){
    ll n, m, k;
    cin >> n >> m >> k;

    vector<vector<ll>> csucsok(n, vector<ll>());
    for(ll i = 0; i < m; i++){
        ll a, b;
        cin >> a >> b;
        a--; b--;

        csucsok[a].push_back(b);
        csucsok[b].push_back(a);
    }

    ll l;
    cin >> l;
    vector<ll> latogat(l);
    for(ll &x : latogat){
        cin >> x;
        x--;
    }

    ll b;
    cin >> b;
    vector<ll> kutak(b);
    for(ll &x : kutak){
        cin >> x;
        x--;
    }

    vector<vector<ll>> kutL(b, vector<ll>(l, INF));
    vector<vector<ll>> kutKut(b, vector<ll>(b, INF));
    for(ll i = 0; i < b; i++){
        vector<ll> d(n, INF);
        queue<ll> bejar;
        bejar.push(kutak[i]);
        d[kutak[i]] = 0;

        while(!bejar.empty()){
            ll akt = bejar.front();
            bejar.pop();

            for(ll x : csucsok[akt]){
                if(d[akt] + 1 < d[x]){
                    d[x] = d[akt] + 1;
                    bejar.push(x);
                }
            }
        }

        for(ll j = 0; j < l; j++){
            if(d[latogat[j]] <= k){
                kutL[i][j] = d[latogat[j]];
            }
        }

        for(ll j = 0; j < b; j++){
            if(d[kutak[j]] <= k){
                kutKut[i][j] = d[kutak[j]];
            }
        }
    }

    for(ll k = 0; k < b; k++){
        for(ll i = 0; i < b; i++){
            for(ll j = 0; j < b; j++){
                kutKut[i][j] = min(kutKut[i][j], kutKut[i][k] + kutKut[k][j]);
            }
        }
    }

    vector<ll> ansA(k + 2);
    ansA[k + 1] = INF;
    for(ll i = 1; i < l; i++){
        vector<ll> ansB(k + 2, INF);
        queue<ll> bejar;
        vector<ll> tavok(n, INF);
        tavok[latogat[i - 1]] = 0;
        bejar.push(latogat[i - 1]);
        while(!bejar.empty()){
            ll akt = bejar.front();
            bejar.pop();

            for(ll x : csucsok[akt]){
                if(tavok[akt] + 1 < tavok[x]){
                    tavok[x] = tavok[akt] + 1;
                    bejar.push(x);
                }
            }
        }

        ll kovi = tavok[latogat[i]];
        for(ll j = 0; j + kovi <= k; j++){
            ansB[j] = min(ansB[j], ansA[j + kovi] + kovi);
        }

        for(ll j = 0; j < b; j++){
            ll marad = k - kutL[j][i];
            if(marad >= 0 && kutL[j][i - 1] <= k){
                ansB[marad] = min(ansB[marad], ansA[kutL[j][i - 1]] + kutL[j][i - 1] + kutL[j][i]);
            }
            for(ll kk = 0; kk < b; kk++){
                ll marad2 = k - kutL[kk][i];
                if(marad2 >= 0 && kutL[kk][i - 1] <= k){
                    ansB[marad2] = min(ansB[marad2], ansA[kutL[j][i - 1]] + kutL[j][i - 1] + kutKut[j][kk] + kutL[kk][i]);
                }
            }
        }

        for(ll j = k - 1; j >= 0; j--){
            ansB[j] = min(ansB[j], ansB[j + 1]);
        }

        ansA = ansB;
    }

    cout << (ansA[0] == INF ? -1 : ansA[0]) << "\n";
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1808 KiB
2Accepted342ms7120 KiB
subtask20/12
3Accepted3ms2360 KiB
4Accepted3ms2552 KiB
5Accepted3ms2640 KiB
6Runtime error3ms2940 KiB
7Runtime error3ms2960 KiB
8Runtime error3ms3236 KiB
9Runtime error3ms3180 KiB
10Runtime error3ms3372 KiB
subtask30/18
11Accepted3ms2360 KiB
12Accepted3ms2552 KiB
13Accepted3ms2640 KiB
14Runtime error3ms2940 KiB
15Runtime error3ms2960 KiB
16Runtime error3ms3236 KiB
17Runtime error3ms3180 KiB
18Runtime error3ms3372 KiB
19Accepted4ms3496 KiB
20Accepted14ms4032 KiB
21Accepted14ms4280 KiB
22Accepted14ms4344 KiB
23Accepted7ms3888 KiB
24Runtime error4ms4044 KiB
25Runtime error6ms4560 KiB
26Runtime error6ms4584 KiB
27Runtime error7ms4668 KiB
subtask40/25
28Accepted3ms2360 KiB
29Accepted3ms2552 KiB
30Accepted3ms2640 KiB
31Runtime error3ms2940 KiB
32Runtime error3ms2960 KiB
33Runtime error3ms3236 KiB
34Runtime error3ms3180 KiB
35Runtime error3ms3372 KiB
36Accepted39ms5072 KiB
37Accepted35ms5060 KiB
38Accepted37ms5188 KiB
39Accepted27ms4900 KiB
40Accepted14ms4848 KiB
41Accepted8ms4892 KiB
42Runtime error34ms5572 KiB
43Runtime error25ms5480 KiB
44Runtime error25ms5476 KiB
45Wrong answer14ms5320 KiB
subtask524/24
46Accepted435ms5264 KiB
47Accepted381ms5132 KiB
48Accepted425ms5168 KiB
49Accepted391ms5420 KiB
50Accepted246ms5356 KiB
51Accepted430ms5376 KiB
52Accepted375ms5372 KiB
53Accepted421ms5316 KiB
54Accepted388ms5316 KiB
55Accepted241ms5288 KiB
subtask60/21
56Accepted3ms2360 KiB
57Accepted3ms2552 KiB
58Accepted3ms2640 KiB
59Runtime error3ms2940 KiB
60Runtime error3ms2960 KiB
61Runtime error3ms3236 KiB
62Runtime error3ms3180 KiB
63Runtime error3ms3372 KiB
64Accepted4ms3496 KiB
65Accepted14ms4032 KiB
66Accepted14ms4280 KiB
67Accepted14ms4344 KiB
68Accepted7ms3888 KiB
69Runtime error4ms4044 KiB
70Runtime error6ms4560 KiB
71Runtime error6ms4584 KiB
72Runtime error7ms4668 KiB
73Accepted39ms5072 KiB
74Accepted35ms5060 KiB
75Accepted37ms5188 KiB
76Accepted27ms4900 KiB
77Accepted14ms4848 KiB
78Accepted8ms4892 KiB
79Runtime error34ms5572 KiB
80Runtime error25ms5480 KiB
81Runtime error25ms5476 KiB
82Wrong answer14ms5320 KiB
83Accepted435ms5264 KiB
84Accepted381ms5132 KiB
85Accepted425ms5168 KiB
86Accepted391ms5420 KiB
87Accepted246ms5356 KiB
88Accepted430ms5376 KiB
89Accepted375ms5372 KiB
90Accepted421ms5316 KiB
91Accepted388ms5316 KiB
92Accepted241ms5288 KiB
93Accepted116ms6736 KiB
94Runtime error28ms6788 KiB
95Runtime error34ms6916 KiB
96Runtime error35ms6932 KiB
97Wrong answer43ms6556 KiB
98Accepted104ms7588 KiB
99Accepted97ms6332 KiB
100Accepted680ms12720 KiB
101Accepted711ms12704 KiB
102Accepted658ms12640 KiB
103Accepted565ms12820 KiB
104Accepted430ms12832 KiB
105Accepted559ms12688 KiB
106Accepted554ms12836 KiB
107Accepted540ms12936 KiB
108Accepted666ms13020 KiB
109Accepted136ms5528 KiB
110Accepted370ms8368 KiB
111Accepted425ms5744 KiB
112Accepted340ms5988 KiB
113Accepted361ms5728 KiB
114Runtime error39ms13136 KiB
115Runtime error34ms6672 KiB
116Runtime error35ms6840 KiB
117Runtime error32ms12828 KiB
118Runtime error187ms12540 KiB