108132024-04-15 14:25:46AblablablaAutó-tortúracpp17Futási hiba 24/100711ms13660 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1680 KiB
2Elfogadva342ms6920 KiB
subtask20/12
3Elfogadva3ms2064 KiB
4Elfogadva3ms2272 KiB
5Elfogadva3ms2352 KiB
6Futási hiba3ms2696 KiB
7Futási hiba3ms2656 KiB
8Futási hiba3ms2912 KiB
9Futási hiba3ms3000 KiB
10Futási hiba3ms3280 KiB
subtask30/18
11Elfogadva3ms2064 KiB
12Elfogadva3ms2272 KiB
13Elfogadva3ms2352 KiB
14Futási hiba3ms2696 KiB
15Futási hiba3ms2656 KiB
16Futási hiba3ms2912 KiB
17Futási hiba3ms3000 KiB
18Futási hiba3ms3280 KiB
19Elfogadva4ms3336 KiB
20Elfogadva14ms3868 KiB
21Elfogadva14ms3828 KiB
22Elfogadva14ms4152 KiB
23Elfogadva7ms3692 KiB
24Futási hiba6ms3984 KiB
25Futási hiba6ms4448 KiB
26Futási hiba6ms4412 KiB
27Futási hiba7ms4308 KiB
subtask40/25
28Elfogadva3ms2064 KiB
29Elfogadva3ms2272 KiB
30Elfogadva3ms2352 KiB
31Futási hiba3ms2696 KiB
32Futási hiba3ms2656 KiB
33Futási hiba3ms2912 KiB
34Futási hiba3ms3000 KiB
35Futási hiba3ms3280 KiB
36Elfogadva37ms4880 KiB
37Elfogadva35ms4872 KiB
38Elfogadva37ms4988 KiB
39Elfogadva27ms4648 KiB
40Elfogadva14ms4456 KiB
41Elfogadva8ms4292 KiB
42Futási hiba34ms5180 KiB
43Futási hiba25ms5372 KiB
44Futási hiba25ms5284 KiB
45Hibás válasz14ms5212 KiB
subtask524/24
46Elfogadva435ms5120 KiB
47Elfogadva381ms5104 KiB
48Elfogadva425ms5408 KiB
49Elfogadva393ms5188 KiB
50Elfogadva246ms5548 KiB
51Elfogadva430ms5736 KiB
52Elfogadva375ms5528 KiB
53Elfogadva421ms5496 KiB
54Elfogadva388ms5340 KiB
55Elfogadva243ms5444 KiB
subtask60/21
56Elfogadva3ms2064 KiB
57Elfogadva3ms2272 KiB
58Elfogadva3ms2352 KiB
59Futási hiba3ms2696 KiB
60Futási hiba3ms2656 KiB
61Futási hiba3ms2912 KiB
62Futási hiba3ms3000 KiB
63Futási hiba3ms3280 KiB
64Elfogadva4ms3336 KiB
65Elfogadva14ms3868 KiB
66Elfogadva14ms3828 KiB
67Elfogadva14ms4152 KiB
68Elfogadva7ms3692 KiB
69Futási hiba6ms3984 KiB
70Futási hiba6ms4448 KiB
71Futási hiba6ms4412 KiB
72Futási hiba7ms4308 KiB
73Elfogadva37ms4880 KiB
74Elfogadva35ms4872 KiB
75Elfogadva37ms4988 KiB
76Elfogadva27ms4648 KiB
77Elfogadva14ms4456 KiB
78Elfogadva8ms4292 KiB
79Futási hiba34ms5180 KiB
80Futási hiba25ms5372 KiB
81Futási hiba25ms5284 KiB
82Hibás válasz14ms5212 KiB
83Elfogadva435ms5120 KiB
84Elfogadva381ms5104 KiB
85Elfogadva425ms5408 KiB
86Elfogadva393ms5188 KiB
87Elfogadva246ms5548 KiB
88Elfogadva430ms5736 KiB
89Elfogadva375ms5528 KiB
90Elfogadva421ms5496 KiB
91Elfogadva388ms5340 KiB
92Elfogadva243ms5444 KiB
93Elfogadva109ms6688 KiB
94Futási hiba28ms7044 KiB
95Futási hiba34ms7284 KiB
96Futási hiba35ms7468 KiB
97Hibás válasz43ms7012 KiB
98Elfogadva104ms8028 KiB
99Elfogadva96ms6844 KiB
100Elfogadva680ms13092 KiB
101Elfogadva711ms13124 KiB
102Elfogadva658ms13212 KiB
103Elfogadva564ms13156 KiB
104Elfogadva430ms13064 KiB
105Elfogadva564ms13112 KiB
106Elfogadva555ms13108 KiB
107Elfogadva540ms13208 KiB
108Elfogadva666ms13304 KiB
109Elfogadva134ms5916 KiB
110Elfogadva372ms8752 KiB
111Elfogadva425ms6160 KiB
112Elfogadva340ms6372 KiB
113Elfogadva363ms6164 KiB
114Futási hiba39ms13660 KiB
115Futási hiba34ms7172 KiB
116Futási hiba35ms7100 KiB
117Futási hiba32ms13116 KiB
118Futási hiba186ms12656 KiB