10813 2024. 04. 15 14:25:46 Ablablabla Autó-tortúra cpp17 Futási hiba 24/100 711ms 13660 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";
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1680 KiB
2 Elfogadva 342ms 6920 KiB
subtask2 0/12
3 Elfogadva 3ms 2064 KiB
4 Elfogadva 3ms 2272 KiB
5 Elfogadva 3ms 2352 KiB
6 Futási hiba 3ms 2696 KiB
7 Futási hiba 3ms 2656 KiB
8 Futási hiba 3ms 2912 KiB
9 Futási hiba 3ms 3000 KiB
10 Futási hiba 3ms 3280 KiB
subtask3 0/18
11 Elfogadva 3ms 2064 KiB
12 Elfogadva 3ms 2272 KiB
13 Elfogadva 3ms 2352 KiB
14 Futási hiba 3ms 2696 KiB
15 Futási hiba 3ms 2656 KiB
16 Futási hiba 3ms 2912 KiB
17 Futási hiba 3ms 3000 KiB
18 Futási hiba 3ms 3280 KiB
19 Elfogadva 4ms 3336 KiB
20 Elfogadva 14ms 3868 KiB
21 Elfogadva 14ms 3828 KiB
22 Elfogadva 14ms 4152 KiB
23 Elfogadva 7ms 3692 KiB
24 Futási hiba 6ms 3984 KiB
25 Futási hiba 6ms 4448 KiB
26 Futási hiba 6ms 4412 KiB
27 Futási hiba 7ms 4308 KiB
subtask4 0/25
28 Elfogadva 3ms 2064 KiB
29 Elfogadva 3ms 2272 KiB
30 Elfogadva 3ms 2352 KiB
31 Futási hiba 3ms 2696 KiB
32 Futási hiba 3ms 2656 KiB
33 Futási hiba 3ms 2912 KiB
34 Futási hiba 3ms 3000 KiB
35 Futási hiba 3ms 3280 KiB
36 Elfogadva 37ms 4880 KiB
37 Elfogadva 35ms 4872 KiB
38 Elfogadva 37ms 4988 KiB
39 Elfogadva 27ms 4648 KiB
40 Elfogadva 14ms 4456 KiB
41 Elfogadva 8ms 4292 KiB
42 Futási hiba 34ms 5180 KiB
43 Futási hiba 25ms 5372 KiB
44 Futási hiba 25ms 5284 KiB
45 Hibás válasz 14ms 5212 KiB
subtask5 24/24
46 Elfogadva 435ms 5120 KiB
47 Elfogadva 381ms 5104 KiB
48 Elfogadva 425ms 5408 KiB
49 Elfogadva 393ms 5188 KiB
50 Elfogadva 246ms 5548 KiB
51 Elfogadva 430ms 5736 KiB
52 Elfogadva 375ms 5528 KiB
53 Elfogadva 421ms 5496 KiB
54 Elfogadva 388ms 5340 KiB
55 Elfogadva 243ms 5444 KiB
subtask6 0/21
56 Elfogadva 3ms 2064 KiB
57 Elfogadva 3ms 2272 KiB
58 Elfogadva 3ms 2352 KiB
59 Futási hiba 3ms 2696 KiB
60 Futási hiba 3ms 2656 KiB
61 Futási hiba 3ms 2912 KiB
62 Futási hiba 3ms 3000 KiB
63 Futási hiba 3ms 3280 KiB
64 Elfogadva 4ms 3336 KiB
65 Elfogadva 14ms 3868 KiB
66 Elfogadva 14ms 3828 KiB
67 Elfogadva 14ms 4152 KiB
68 Elfogadva 7ms 3692 KiB
69 Futási hiba 6ms 3984 KiB
70 Futási hiba 6ms 4448 KiB
71 Futási hiba 6ms 4412 KiB
72 Futási hiba 7ms 4308 KiB
73 Elfogadva 37ms 4880 KiB
74 Elfogadva 35ms 4872 KiB
75 Elfogadva 37ms 4988 KiB
76 Elfogadva 27ms 4648 KiB
77 Elfogadva 14ms 4456 KiB
78 Elfogadva 8ms 4292 KiB
79 Futási hiba 34ms 5180 KiB
80 Futási hiba 25ms 5372 KiB
81 Futási hiba 25ms 5284 KiB
82 Hibás válasz 14ms 5212 KiB
83 Elfogadva 435ms 5120 KiB
84 Elfogadva 381ms 5104 KiB
85 Elfogadva 425ms 5408 KiB
86 Elfogadva 393ms 5188 KiB
87 Elfogadva 246ms 5548 KiB
88 Elfogadva 430ms 5736 KiB
89 Elfogadva 375ms 5528 KiB
90 Elfogadva 421ms 5496 KiB
91 Elfogadva 388ms 5340 KiB
92 Elfogadva 243ms 5444 KiB
93 Elfogadva 109ms 6688 KiB
94 Futási hiba 28ms 7044 KiB
95 Futási hiba 34ms 7284 KiB
96 Futási hiba 35ms 7468 KiB
97 Hibás válasz 43ms 7012 KiB
98 Elfogadva 104ms 8028 KiB
99 Elfogadva 96ms 6844 KiB
100 Elfogadva 680ms 13092 KiB
101 Elfogadva 711ms 13124 KiB
102 Elfogadva 658ms 13212 KiB
103 Elfogadva 564ms 13156 KiB
104 Elfogadva 430ms 13064 KiB
105 Elfogadva 564ms 13112 KiB
106 Elfogadva 555ms 13108 KiB
107 Elfogadva 540ms 13208 KiB
108 Elfogadva 666ms 13304 KiB
109 Elfogadva 134ms 5916 KiB
110 Elfogadva 372ms 8752 KiB
111 Elfogadva 425ms 6160 KiB
112 Elfogadva 340ms 6372 KiB
113 Elfogadva 363ms 6164 KiB
114 Futási hiba 39ms 13660 KiB
115 Futási hiba 34ms 7172 KiB
116 Futási hiba 35ms 7100 KiB
117 Futási hiba 32ms 13116 KiB
118 Futási hiba 186ms 12656 KiB