108292024-04-16 09:17:29AblablablaAutó-tortúracpp17Wrong answer 24/100728ms13224 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 o = 0; o < b; o++){
        for(ll i = 0; i < b; i++){
            for(ll j = 0; j < b; j++){
                kutKut[i][j] = min(kutKut[i][j], kutKut[i][o] + kutKut[o][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 && kutL[j][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
1Accepted3ms1936 KiB
2Accepted351ms7104 KiB
subtask20/12
3Accepted3ms2248 KiB
4Accepted3ms2460 KiB
5Accepted3ms2612 KiB
6Accepted3ms2924 KiB
7Accepted2ms2868 KiB
8Wrong answer2ms3004 KiB
9Wrong answer3ms2868 KiB
10Accepted3ms3112 KiB
subtask30/18
11Accepted3ms2248 KiB
12Accepted3ms2460 KiB
13Accepted3ms2612 KiB
14Accepted3ms2924 KiB
15Accepted2ms2868 KiB
16Wrong answer2ms3004 KiB
17Wrong answer3ms2868 KiB
18Accepted3ms3112 KiB
19Accepted4ms3136 KiB
20Accepted16ms3632 KiB
21Accepted14ms3940 KiB
22Accepted14ms3884 KiB
23Accepted8ms3796 KiB
24Wrong answer6ms3796 KiB
25Wrong answer14ms4100 KiB
26Wrong answer12ms4052 KiB
27Wrong answer7ms4172 KiB
subtask40/25
28Accepted3ms2248 KiB
29Accepted3ms2460 KiB
30Accepted3ms2612 KiB
31Accepted3ms2924 KiB
32Accepted2ms2868 KiB
33Wrong answer2ms3004 KiB
34Wrong answer3ms2868 KiB
35Accepted3ms3112 KiB
36Accepted39ms4864 KiB
37Accepted35ms5088 KiB
38Accepted37ms5116 KiB
39Accepted27ms4852 KiB
40Accepted14ms4676 KiB
41Accepted8ms4576 KiB
42Wrong answer37ms5380 KiB
43Accepted28ms5172 KiB
44Wrong answer28ms5408 KiB
45Wrong answer14ms5408 KiB
subtask524/24
46Accepted435ms5204 KiB
47Accepted379ms5184 KiB
48Accepted425ms5384 KiB
49Accepted393ms5384 KiB
50Accepted247ms5336 KiB
51Accepted430ms5352 KiB
52Accepted375ms5288 KiB
53Accepted423ms5332 KiB
54Accepted388ms5440 KiB
55Accepted243ms5532 KiB
subtask60/21
56Accepted3ms2248 KiB
57Accepted3ms2460 KiB
58Accepted3ms2612 KiB
59Accepted3ms2924 KiB
60Accepted2ms2868 KiB
61Wrong answer2ms3004 KiB
62Wrong answer3ms2868 KiB
63Accepted3ms3112 KiB
64Accepted4ms3136 KiB
65Accepted16ms3632 KiB
66Accepted14ms3940 KiB
67Accepted14ms3884 KiB
68Accepted8ms3796 KiB
69Wrong answer6ms3796 KiB
70Wrong answer14ms4100 KiB
71Wrong answer12ms4052 KiB
72Wrong answer7ms4172 KiB
73Accepted39ms4864 KiB
74Accepted35ms5088 KiB
75Accepted37ms5116 KiB
76Accepted27ms4852 KiB
77Accepted14ms4676 KiB
78Accepted8ms4576 KiB
79Wrong answer37ms5380 KiB
80Accepted28ms5172 KiB
81Wrong answer28ms5408 KiB
82Wrong answer14ms5408 KiB
83Accepted435ms5204 KiB
84Accepted379ms5184 KiB
85Accepted425ms5384 KiB
86Accepted393ms5384 KiB
87Accepted247ms5336 KiB
88Accepted430ms5352 KiB
89Accepted375ms5288 KiB
90Accepted423ms5332 KiB
91Accepted388ms5440 KiB
92Accepted243ms5532 KiB
93Accepted112ms6784 KiB
94Wrong answer109ms6784 KiB
95Wrong answer133ms7016 KiB
96Wrong answer140ms7016 KiB
97Wrong answer43ms6568 KiB
98Accepted129ms7684 KiB
99Accepted97ms6500 KiB
100Accepted699ms12972 KiB
101Accepted728ms12964 KiB
102Accepted679ms13044 KiB
103Accepted584ms13088 KiB
104Accepted449ms12988 KiB
105Accepted578ms12960 KiB
106Accepted573ms13096 KiB
107Accepted612ms13032 KiB
108Accepted689ms13224 KiB
109Accepted136ms5668 KiB
110Accepted375ms8352 KiB
111Accepted425ms5764 KiB
112Accepted340ms6028 KiB
113Accepted363ms5772 KiB
114Wrong answer634ms12980 KiB
115Wrong answer93ms6740 KiB
116Wrong answer96ms6716 KiB
117Wrong answer572ms12944 KiB
118Wrong answer190ms12620 KiB