108302024-04-16 09:24:15AblablablaAutó-tortúracpp17Accepted 100/100712ms13460 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[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
1Accepted3ms1812 KiB
2Accepted344ms7068 KiB
subtask212/12
3Accepted3ms2084 KiB
4Accepted3ms2336 KiB
5Accepted3ms2576 KiB
6Accepted3ms2788 KiB
7Accepted3ms2756 KiB
8Accepted3ms2852 KiB
9Accepted3ms2936 KiB
10Accepted3ms3064 KiB
subtask318/18
11Accepted3ms2084 KiB
12Accepted3ms2336 KiB
13Accepted3ms2576 KiB
14Accepted3ms2788 KiB
15Accepted3ms2756 KiB
16Accepted3ms2852 KiB
17Accepted3ms2936 KiB
18Accepted3ms3064 KiB
19Accepted4ms3480 KiB
20Accepted14ms3928 KiB
21Accepted14ms4248 KiB
22Accepted14ms4452 KiB
23Accepted7ms4168 KiB
24Accepted6ms4104 KiB
25Accepted14ms4568 KiB
26Accepted12ms4544 KiB
27Accepted7ms4468 KiB
subtask425/25
28Accepted3ms2084 KiB
29Accepted3ms2336 KiB
30Accepted3ms2576 KiB
31Accepted3ms2788 KiB
32Accepted3ms2756 KiB
33Accepted3ms2852 KiB
34Accepted3ms2936 KiB
35Accepted3ms3064 KiB
36Accepted39ms4928 KiB
37Accepted35ms4912 KiB
38Accepted37ms5040 KiB
39Accepted27ms4800 KiB
40Accepted14ms4748 KiB
41Accepted8ms4804 KiB
42Accepted37ms5564 KiB
43Accepted28ms5480 KiB
44Accepted28ms5444 KiB
45Accepted14ms5136 KiB
subtask524/24
46Accepted439ms5308 KiB
47Accepted386ms5296 KiB
48Accepted430ms5284 KiB
49Accepted400ms5536 KiB
50Accepted241ms5388 KiB
51Accepted435ms5404 KiB
52Accepted382ms5344 KiB
53Accepted425ms5360 KiB
54Accepted395ms5372 KiB
55Accepted237ms5352 KiB
subtask621/21
56Accepted3ms2084 KiB
57Accepted3ms2336 KiB
58Accepted3ms2576 KiB
59Accepted3ms2788 KiB
60Accepted3ms2756 KiB
61Accepted3ms2852 KiB
62Accepted3ms2936 KiB
63Accepted3ms3064 KiB
64Accepted4ms3480 KiB
65Accepted14ms3928 KiB
66Accepted14ms4248 KiB
67Accepted14ms4452 KiB
68Accepted7ms4168 KiB
69Accepted6ms4104 KiB
70Accepted14ms4568 KiB
71Accepted12ms4544 KiB
72Accepted7ms4468 KiB
73Accepted39ms4928 KiB
74Accepted35ms4912 KiB
75Accepted37ms5040 KiB
76Accepted27ms4800 KiB
77Accepted14ms4748 KiB
78Accepted8ms4804 KiB
79Accepted37ms5564 KiB
80Accepted28ms5480 KiB
81Accepted28ms5444 KiB
82Accepted14ms5136 KiB
83Accepted439ms5308 KiB
84Accepted386ms5296 KiB
85Accepted430ms5284 KiB
86Accepted400ms5536 KiB
87Accepted241ms5388 KiB
88Accepted435ms5404 KiB
89Accepted382ms5344 KiB
90Accepted425ms5360 KiB
91Accepted395ms5372 KiB
92Accepted237ms5352 KiB
93Accepted111ms6772 KiB
94Accepted108ms6908 KiB
95Accepted145ms7352 KiB
96Accepted137ms7212 KiB
97Accepted43ms6988 KiB
98Accepted104ms8116 KiB
99Accepted96ms6768 KiB
100Accepted680ms13364 KiB
101Accepted712ms13460 KiB
102Accepted657ms13252 KiB
103Accepted574ms13132 KiB
104Accepted435ms13080 KiB
105Accepted565ms13124 KiB
106Accepted560ms13052 KiB
107Accepted551ms13148 KiB
108Accepted674ms13148 KiB
109Accepted136ms5692 KiB
110Accepted379ms8540 KiB
111Accepted437ms5964 KiB
112Accepted349ms6220 KiB
113Accepted374ms5920 KiB
114Accepted625ms13328 KiB
115Accepted93ms6912 KiB
116Accepted93ms6832 KiB
117Accepted523ms12960 KiB
118Accepted187ms12640 KiB