10814 2024. 04. 15 14:26:40 Ablablabla Autó-tortúra cpp17 Futási hiba 24/100 711ms 13136 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 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 1808 KiB
2 Elfogadva 342ms 7120 KiB
subtask2 0/12
3 Elfogadva 3ms 2360 KiB
4 Elfogadva 3ms 2552 KiB
5 Elfogadva 3ms 2640 KiB
6 Futási hiba 3ms 2940 KiB
7 Futási hiba 3ms 2960 KiB
8 Futási hiba 3ms 3236 KiB
9 Futási hiba 3ms 3180 KiB
10 Futási hiba 3ms 3372 KiB
subtask3 0/18
11 Elfogadva 3ms 2360 KiB
12 Elfogadva 3ms 2552 KiB
13 Elfogadva 3ms 2640 KiB
14 Futási hiba 3ms 2940 KiB
15 Futási hiba 3ms 2960 KiB
16 Futási hiba 3ms 3236 KiB
17 Futási hiba 3ms 3180 KiB
18 Futási hiba 3ms 3372 KiB
19 Elfogadva 4ms 3496 KiB
20 Elfogadva 14ms 4032 KiB
21 Elfogadva 14ms 4280 KiB
22 Elfogadva 14ms 4344 KiB
23 Elfogadva 7ms 3888 KiB
24 Futási hiba 4ms 4044 KiB
25 Futási hiba 6ms 4560 KiB
26 Futási hiba 6ms 4584 KiB
27 Futási hiba 7ms 4668 KiB
subtask4 0/25
28 Elfogadva 3ms 2360 KiB
29 Elfogadva 3ms 2552 KiB
30 Elfogadva 3ms 2640 KiB
31 Futási hiba 3ms 2940 KiB
32 Futási hiba 3ms 2960 KiB
33 Futási hiba 3ms 3236 KiB
34 Futási hiba 3ms 3180 KiB
35 Futási hiba 3ms 3372 KiB
36 Elfogadva 39ms 5072 KiB
37 Elfogadva 35ms 5060 KiB
38 Elfogadva 37ms 5188 KiB
39 Elfogadva 27ms 4900 KiB
40 Elfogadva 14ms 4848 KiB
41 Elfogadva 8ms 4892 KiB
42 Futási hiba 34ms 5572 KiB
43 Futási hiba 25ms 5480 KiB
44 Futási hiba 25ms 5476 KiB
45 Hibás válasz 14ms 5320 KiB
subtask5 24/24
46 Elfogadva 435ms 5264 KiB
47 Elfogadva 381ms 5132 KiB
48 Elfogadva 425ms 5168 KiB
49 Elfogadva 391ms 5420 KiB
50 Elfogadva 246ms 5356 KiB
51 Elfogadva 430ms 5376 KiB
52 Elfogadva 375ms 5372 KiB
53 Elfogadva 421ms 5316 KiB
54 Elfogadva 388ms 5316 KiB
55 Elfogadva 241ms 5288 KiB
subtask6 0/21
56 Elfogadva 3ms 2360 KiB
57 Elfogadva 3ms 2552 KiB
58 Elfogadva 3ms 2640 KiB
59 Futási hiba 3ms 2940 KiB
60 Futási hiba 3ms 2960 KiB
61 Futási hiba 3ms 3236 KiB
62 Futási hiba 3ms 3180 KiB
63 Futási hiba 3ms 3372 KiB
64 Elfogadva 4ms 3496 KiB
65 Elfogadva 14ms 4032 KiB
66 Elfogadva 14ms 4280 KiB
67 Elfogadva 14ms 4344 KiB
68 Elfogadva 7ms 3888 KiB
69 Futási hiba 4ms 4044 KiB
70 Futási hiba 6ms 4560 KiB
71 Futási hiba 6ms 4584 KiB
72 Futási hiba 7ms 4668 KiB
73 Elfogadva 39ms 5072 KiB
74 Elfogadva 35ms 5060 KiB
75 Elfogadva 37ms 5188 KiB
76 Elfogadva 27ms 4900 KiB
77 Elfogadva 14ms 4848 KiB
78 Elfogadva 8ms 4892 KiB
79 Futási hiba 34ms 5572 KiB
80 Futási hiba 25ms 5480 KiB
81 Futási hiba 25ms 5476 KiB
82 Hibás válasz 14ms 5320 KiB
83 Elfogadva 435ms 5264 KiB
84 Elfogadva 381ms 5132 KiB
85 Elfogadva 425ms 5168 KiB
86 Elfogadva 391ms 5420 KiB
87 Elfogadva 246ms 5356 KiB
88 Elfogadva 430ms 5376 KiB
89 Elfogadva 375ms 5372 KiB
90 Elfogadva 421ms 5316 KiB
91 Elfogadva 388ms 5316 KiB
92 Elfogadva 241ms 5288 KiB
93 Elfogadva 116ms 6736 KiB
94 Futási hiba 28ms 6788 KiB
95 Futási hiba 34ms 6916 KiB
96 Futási hiba 35ms 6932 KiB
97 Hibás válasz 43ms 6556 KiB
98 Elfogadva 104ms 7588 KiB
99 Elfogadva 97ms 6332 KiB
100 Elfogadva 680ms 12720 KiB
101 Elfogadva 711ms 12704 KiB
102 Elfogadva 658ms 12640 KiB
103 Elfogadva 565ms 12820 KiB
104 Elfogadva 430ms 12832 KiB
105 Elfogadva 559ms 12688 KiB
106 Elfogadva 554ms 12836 KiB
107 Elfogadva 540ms 12936 KiB
108 Elfogadva 666ms 13020 KiB
109 Elfogadva 136ms 5528 KiB
110 Elfogadva 370ms 8368 KiB
111 Elfogadva 425ms 5744 KiB
112 Elfogadva 340ms 5988 KiB
113 Elfogadva 361ms 5728 KiB
114 Futási hiba 39ms 13136 KiB
115 Futási hiba 34ms 6672 KiB
116 Futási hiba 35ms 6840 KiB
117 Futási hiba 32ms 12828 KiB
118 Futási hiba 187ms 12540 KiB