108132024-04-15 14:25:46AblablablaAutó-tortúracpp17Runtime error 24/100711ms13660 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF = 1e18;

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
1Accepted3ms1680 KiB
2Accepted342ms6920 KiB
subtask20/12
3Accepted3ms2064 KiB
4Accepted3ms2272 KiB
5Accepted3ms2352 KiB
6Runtime error3ms2696 KiB
7Runtime error3ms2656 KiB
8Runtime error3ms2912 KiB
9Runtime error3ms3000 KiB
10Runtime error3ms3280 KiB
subtask30/18
11Accepted3ms2064 KiB
12Accepted3ms2272 KiB
13Accepted3ms2352 KiB
14Runtime error3ms2696 KiB
15Runtime error3ms2656 KiB
16Runtime error3ms2912 KiB
17Runtime error3ms3000 KiB
18Runtime error3ms3280 KiB
19Accepted4ms3336 KiB
20Accepted14ms3868 KiB
21Accepted14ms3828 KiB
22Accepted14ms4152 KiB
23Accepted7ms3692 KiB
24Runtime error6ms3984 KiB
25Runtime error6ms4448 KiB
26Runtime error6ms4412 KiB
27Runtime error7ms4308 KiB
subtask40/25
28Accepted3ms2064 KiB
29Accepted3ms2272 KiB
30Accepted3ms2352 KiB
31Runtime error3ms2696 KiB
32Runtime error3ms2656 KiB
33Runtime error3ms2912 KiB
34Runtime error3ms3000 KiB
35Runtime error3ms3280 KiB
36Accepted37ms4880 KiB
37Accepted35ms4872 KiB
38Accepted37ms4988 KiB
39Accepted27ms4648 KiB
40Accepted14ms4456 KiB
41Accepted8ms4292 KiB
42Runtime error34ms5180 KiB
43Runtime error25ms5372 KiB
44Runtime error25ms5284 KiB
45Wrong answer14ms5212 KiB
subtask524/24
46Accepted435ms5120 KiB
47Accepted381ms5104 KiB
48Accepted425ms5408 KiB
49Accepted393ms5188 KiB
50Accepted246ms5548 KiB
51Accepted430ms5736 KiB
52Accepted375ms5528 KiB
53Accepted421ms5496 KiB
54Accepted388ms5340 KiB
55Accepted243ms5444 KiB
subtask60/21
56Accepted3ms2064 KiB
57Accepted3ms2272 KiB
58Accepted3ms2352 KiB
59Runtime error3ms2696 KiB
60Runtime error3ms2656 KiB
61Runtime error3ms2912 KiB
62Runtime error3ms3000 KiB
63Runtime error3ms3280 KiB
64Accepted4ms3336 KiB
65Accepted14ms3868 KiB
66Accepted14ms3828 KiB
67Accepted14ms4152 KiB
68Accepted7ms3692 KiB
69Runtime error6ms3984 KiB
70Runtime error6ms4448 KiB
71Runtime error6ms4412 KiB
72Runtime error7ms4308 KiB
73Accepted37ms4880 KiB
74Accepted35ms4872 KiB
75Accepted37ms4988 KiB
76Accepted27ms4648 KiB
77Accepted14ms4456 KiB
78Accepted8ms4292 KiB
79Runtime error34ms5180 KiB
80Runtime error25ms5372 KiB
81Runtime error25ms5284 KiB
82Wrong answer14ms5212 KiB
83Accepted435ms5120 KiB
84Accepted381ms5104 KiB
85Accepted425ms5408 KiB
86Accepted393ms5188 KiB
87Accepted246ms5548 KiB
88Accepted430ms5736 KiB
89Accepted375ms5528 KiB
90Accepted421ms5496 KiB
91Accepted388ms5340 KiB
92Accepted243ms5444 KiB
93Accepted109ms6688 KiB
94Runtime error28ms7044 KiB
95Runtime error34ms7284 KiB
96Runtime error35ms7468 KiB
97Wrong answer43ms7012 KiB
98Accepted104ms8028 KiB
99Accepted96ms6844 KiB
100Accepted680ms13092 KiB
101Accepted711ms13124 KiB
102Accepted658ms13212 KiB
103Accepted564ms13156 KiB
104Accepted430ms13064 KiB
105Accepted564ms13112 KiB
106Accepted555ms13108 KiB
107Accepted540ms13208 KiB
108Accepted666ms13304 KiB
109Accepted134ms5916 KiB
110Accepted372ms8752 KiB
111Accepted425ms6160 KiB
112Accepted340ms6372 KiB
113Accepted363ms6164 KiB
114Runtime error39ms13660 KiB
115Runtime error34ms7172 KiB
116Runtime error35ms7100 KiB
117Runtime error32ms13116 KiB
118Runtime error186ms12656 KiB