10815 2024. 04. 15 14:57:37 Ablablabla Autó-tortúra cpp17 Hibás válasz 24/100 759ms 13296 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 && 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 1960 KiB
2 Elfogadva 351ms 7384 KiB
subtask2 0/12
3 Elfogadva 3ms 2468 KiB
4 Elfogadva 2ms 2488 KiB
5 Elfogadva 3ms 2492 KiB
6 Elfogadva 3ms 2708 KiB
7 Elfogadva 3ms 2908 KiB
8 Hibás válasz 3ms 3120 KiB
9 Hibás válasz 3ms 3380 KiB
10 Elfogadva 3ms 3504 KiB
subtask3 0/18
11 Elfogadva 3ms 2468 KiB
12 Elfogadva 2ms 2488 KiB
13 Elfogadva 3ms 2492 KiB
14 Elfogadva 3ms 2708 KiB
15 Elfogadva 3ms 2908 KiB
16 Hibás válasz 3ms 3120 KiB
17 Hibás válasz 3ms 3380 KiB
18 Elfogadva 3ms 3504 KiB
19 Elfogadva 4ms 3656 KiB
20 Elfogadva 16ms 4408 KiB
21 Elfogadva 14ms 4320 KiB
22 Elfogadva 14ms 4580 KiB
23 Elfogadva 7ms 4480 KiB
24 Hibás válasz 6ms 4608 KiB
25 Hibás válasz 14ms 5080 KiB
26 Hibás válasz 12ms 5144 KiB
27 Hibás válasz 7ms 4908 KiB
subtask4 0/25
28 Elfogadva 3ms 2468 KiB
29 Elfogadva 2ms 2488 KiB
30 Elfogadva 3ms 2492 KiB
31 Elfogadva 3ms 2708 KiB
32 Elfogadva 3ms 2908 KiB
33 Hibás válasz 3ms 3120 KiB
34 Hibás válasz 3ms 3380 KiB
35 Elfogadva 3ms 3504 KiB
36 Elfogadva 39ms 5644 KiB
37 Elfogadva 35ms 5724 KiB
38 Elfogadva 39ms 5872 KiB
39 Elfogadva 27ms 5712 KiB
40 Elfogadva 14ms 5436 KiB
41 Elfogadva 8ms 5348 KiB
42 Hibás válasz 37ms 5904 KiB
43 Elfogadva 28ms 6072 KiB
44 Hibás válasz 28ms 5996 KiB
45 Hibás válasz 14ms 5928 KiB
subtask5 24/24
46 Elfogadva 435ms 5788 KiB
47 Elfogadva 379ms 5916 KiB
48 Elfogadva 425ms 6096 KiB
49 Elfogadva 393ms 5964 KiB
50 Elfogadva 247ms 5880 KiB
51 Elfogadva 432ms 5768 KiB
52 Elfogadva 375ms 5752 KiB
53 Elfogadva 421ms 5916 KiB
54 Elfogadva 388ms 5800 KiB
55 Elfogadva 244ms 5668 KiB
subtask6 0/21
56 Elfogadva 3ms 2468 KiB
57 Elfogadva 2ms 2488 KiB
58 Elfogadva 3ms 2492 KiB
59 Elfogadva 3ms 2708 KiB
60 Elfogadva 3ms 2908 KiB
61 Hibás válasz 3ms 3120 KiB
62 Hibás válasz 3ms 3380 KiB
63 Elfogadva 3ms 3504 KiB
64 Elfogadva 4ms 3656 KiB
65 Elfogadva 16ms 4408 KiB
66 Elfogadva 14ms 4320 KiB
67 Elfogadva 14ms 4580 KiB
68 Elfogadva 7ms 4480 KiB
69 Hibás válasz 6ms 4608 KiB
70 Hibás válasz 14ms 5080 KiB
71 Hibás válasz 12ms 5144 KiB
72 Hibás válasz 7ms 4908 KiB
73 Elfogadva 39ms 5644 KiB
74 Elfogadva 35ms 5724 KiB
75 Elfogadva 39ms 5872 KiB
76 Elfogadva 27ms 5712 KiB
77 Elfogadva 14ms 5436 KiB
78 Elfogadva 8ms 5348 KiB
79 Hibás válasz 37ms 5904 KiB
80 Elfogadva 28ms 6072 KiB
81 Hibás válasz 28ms 5996 KiB
82 Hibás válasz 14ms 5928 KiB
83 Elfogadva 435ms 5788 KiB
84 Elfogadva 379ms 5916 KiB
85 Elfogadva 425ms 6096 KiB
86 Elfogadva 393ms 5964 KiB
87 Elfogadva 247ms 5880 KiB
88 Elfogadva 432ms 5768 KiB
89 Elfogadva 375ms 5752 KiB
90 Elfogadva 421ms 5916 KiB
91 Elfogadva 388ms 5800 KiB
92 Elfogadva 244ms 5668 KiB
93 Elfogadva 112ms 7080 KiB
94 Hibás válasz 109ms 7220 KiB
95 Hibás válasz 133ms 7164 KiB
96 Hibás válasz 140ms 7196 KiB
97 Hibás válasz 45ms 6964 KiB
98 Elfogadva 109ms 8228 KiB
99 Elfogadva 97ms 6964 KiB
100 Elfogadva 759ms 13296 KiB
101 Elfogadva 728ms 13080 KiB
102 Elfogadva 677ms 13020 KiB
103 Elfogadva 584ms 13072 KiB
104 Elfogadva 449ms 13180 KiB
105 Elfogadva 642ms 13152 KiB
106 Elfogadva 572ms 13148 KiB
107 Elfogadva 559ms 13080 KiB
108 Elfogadva 688ms 13080 KiB
109 Elfogadva 135ms 5776 KiB
110 Elfogadva 375ms 8504 KiB
111 Elfogadva 425ms 5976 KiB
112 Elfogadva 340ms 6104 KiB
113 Elfogadva 363ms 5704 KiB
114 Hibás válasz 633ms 13104 KiB
115 Hibás válasz 94ms 6724 KiB
116 Hibás válasz 96ms 6648 KiB
117 Hibás válasz 570ms 13008 KiB
118 Hibás válasz 192ms 12744 KiB