10830 2024. 04. 16 09:24:15 Ablablabla Autó-tortúra cpp17 Elfogadva 100/100 712ms 13460 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";
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1812 KiB
2 Elfogadva 344ms 7068 KiB
subtask2 12/12
3 Elfogadva 3ms 2084 KiB
4 Elfogadva 3ms 2336 KiB
5 Elfogadva 3ms 2576 KiB
6 Elfogadva 3ms 2788 KiB
7 Elfogadva 3ms 2756 KiB
8 Elfogadva 3ms 2852 KiB
9 Elfogadva 3ms 2936 KiB
10 Elfogadva 3ms 3064 KiB
subtask3 18/18
11 Elfogadva 3ms 2084 KiB
12 Elfogadva 3ms 2336 KiB
13 Elfogadva 3ms 2576 KiB
14 Elfogadva 3ms 2788 KiB
15 Elfogadva 3ms 2756 KiB
16 Elfogadva 3ms 2852 KiB
17 Elfogadva 3ms 2936 KiB
18 Elfogadva 3ms 3064 KiB
19 Elfogadva 4ms 3480 KiB
20 Elfogadva 14ms 3928 KiB
21 Elfogadva 14ms 4248 KiB
22 Elfogadva 14ms 4452 KiB
23 Elfogadva 7ms 4168 KiB
24 Elfogadva 6ms 4104 KiB
25 Elfogadva 14ms 4568 KiB
26 Elfogadva 12ms 4544 KiB
27 Elfogadva 7ms 4468 KiB
subtask4 25/25
28 Elfogadva 3ms 2084 KiB
29 Elfogadva 3ms 2336 KiB
30 Elfogadva 3ms 2576 KiB
31 Elfogadva 3ms 2788 KiB
32 Elfogadva 3ms 2756 KiB
33 Elfogadva 3ms 2852 KiB
34 Elfogadva 3ms 2936 KiB
35 Elfogadva 3ms 3064 KiB
36 Elfogadva 39ms 4928 KiB
37 Elfogadva 35ms 4912 KiB
38 Elfogadva 37ms 5040 KiB
39 Elfogadva 27ms 4800 KiB
40 Elfogadva 14ms 4748 KiB
41 Elfogadva 8ms 4804 KiB
42 Elfogadva 37ms 5564 KiB
43 Elfogadva 28ms 5480 KiB
44 Elfogadva 28ms 5444 KiB
45 Elfogadva 14ms 5136 KiB
subtask5 24/24
46 Elfogadva 439ms 5308 KiB
47 Elfogadva 386ms 5296 KiB
48 Elfogadva 430ms 5284 KiB
49 Elfogadva 400ms 5536 KiB
50 Elfogadva 241ms 5388 KiB
51 Elfogadva 435ms 5404 KiB
52 Elfogadva 382ms 5344 KiB
53 Elfogadva 425ms 5360 KiB
54 Elfogadva 395ms 5372 KiB
55 Elfogadva 237ms 5352 KiB
subtask6 21/21
56 Elfogadva 3ms 2084 KiB
57 Elfogadva 3ms 2336 KiB
58 Elfogadva 3ms 2576 KiB
59 Elfogadva 3ms 2788 KiB
60 Elfogadva 3ms 2756 KiB
61 Elfogadva 3ms 2852 KiB
62 Elfogadva 3ms 2936 KiB
63 Elfogadva 3ms 3064 KiB
64 Elfogadva 4ms 3480 KiB
65 Elfogadva 14ms 3928 KiB
66 Elfogadva 14ms 4248 KiB
67 Elfogadva 14ms 4452 KiB
68 Elfogadva 7ms 4168 KiB
69 Elfogadva 6ms 4104 KiB
70 Elfogadva 14ms 4568 KiB
71 Elfogadva 12ms 4544 KiB
72 Elfogadva 7ms 4468 KiB
73 Elfogadva 39ms 4928 KiB
74 Elfogadva 35ms 4912 KiB
75 Elfogadva 37ms 5040 KiB
76 Elfogadva 27ms 4800 KiB
77 Elfogadva 14ms 4748 KiB
78 Elfogadva 8ms 4804 KiB
79 Elfogadva 37ms 5564 KiB
80 Elfogadva 28ms 5480 KiB
81 Elfogadva 28ms 5444 KiB
82 Elfogadva 14ms 5136 KiB
83 Elfogadva 439ms 5308 KiB
84 Elfogadva 386ms 5296 KiB
85 Elfogadva 430ms 5284 KiB
86 Elfogadva 400ms 5536 KiB
87 Elfogadva 241ms 5388 KiB
88 Elfogadva 435ms 5404 KiB
89 Elfogadva 382ms 5344 KiB
90 Elfogadva 425ms 5360 KiB
91 Elfogadva 395ms 5372 KiB
92 Elfogadva 237ms 5352 KiB
93 Elfogadva 111ms 6772 KiB
94 Elfogadva 108ms 6908 KiB
95 Elfogadva 145ms 7352 KiB
96 Elfogadva 137ms 7212 KiB
97 Elfogadva 43ms 6988 KiB
98 Elfogadva 104ms 8116 KiB
99 Elfogadva 96ms 6768 KiB
100 Elfogadva 680ms 13364 KiB
101 Elfogadva 712ms 13460 KiB
102 Elfogadva 657ms 13252 KiB
103 Elfogadva 574ms 13132 KiB
104 Elfogadva 435ms 13080 KiB
105 Elfogadva 565ms 13124 KiB
106 Elfogadva 560ms 13052 KiB
107 Elfogadva 551ms 13148 KiB
108 Elfogadva 674ms 13148 KiB
109 Elfogadva 136ms 5692 KiB
110 Elfogadva 379ms 8540 KiB
111 Elfogadva 437ms 5964 KiB
112 Elfogadva 349ms 6220 KiB
113 Elfogadva 374ms 5920 KiB
114 Elfogadva 625ms 13328 KiB
115 Elfogadva 93ms 6912 KiB
116 Elfogadva 93ms 6832 KiB
117 Elfogadva 523ms 12960 KiB
118 Elfogadva 187ms 12640 KiB