108142024-04-15 14:26:40AblablablaAutó-tortúracpp17Futási hiba 24/100711ms13136 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1808 KiB
2Elfogadva342ms7120 KiB
subtask20/12
3Elfogadva3ms2360 KiB
4Elfogadva3ms2552 KiB
5Elfogadva3ms2640 KiB
6Futási hiba3ms2940 KiB
7Futási hiba3ms2960 KiB
8Futási hiba3ms3236 KiB
9Futási hiba3ms3180 KiB
10Futási hiba3ms3372 KiB
subtask30/18
11Elfogadva3ms2360 KiB
12Elfogadva3ms2552 KiB
13Elfogadva3ms2640 KiB
14Futási hiba3ms2940 KiB
15Futási hiba3ms2960 KiB
16Futási hiba3ms3236 KiB
17Futási hiba3ms3180 KiB
18Futási hiba3ms3372 KiB
19Elfogadva4ms3496 KiB
20Elfogadva14ms4032 KiB
21Elfogadva14ms4280 KiB
22Elfogadva14ms4344 KiB
23Elfogadva7ms3888 KiB
24Futási hiba4ms4044 KiB
25Futási hiba6ms4560 KiB
26Futási hiba6ms4584 KiB
27Futási hiba7ms4668 KiB
subtask40/25
28Elfogadva3ms2360 KiB
29Elfogadva3ms2552 KiB
30Elfogadva3ms2640 KiB
31Futási hiba3ms2940 KiB
32Futási hiba3ms2960 KiB
33Futási hiba3ms3236 KiB
34Futási hiba3ms3180 KiB
35Futási hiba3ms3372 KiB
36Elfogadva39ms5072 KiB
37Elfogadva35ms5060 KiB
38Elfogadva37ms5188 KiB
39Elfogadva27ms4900 KiB
40Elfogadva14ms4848 KiB
41Elfogadva8ms4892 KiB
42Futási hiba34ms5572 KiB
43Futási hiba25ms5480 KiB
44Futási hiba25ms5476 KiB
45Hibás válasz14ms5320 KiB
subtask524/24
46Elfogadva435ms5264 KiB
47Elfogadva381ms5132 KiB
48Elfogadva425ms5168 KiB
49Elfogadva391ms5420 KiB
50Elfogadva246ms5356 KiB
51Elfogadva430ms5376 KiB
52Elfogadva375ms5372 KiB
53Elfogadva421ms5316 KiB
54Elfogadva388ms5316 KiB
55Elfogadva241ms5288 KiB
subtask60/21
56Elfogadva3ms2360 KiB
57Elfogadva3ms2552 KiB
58Elfogadva3ms2640 KiB
59Futási hiba3ms2940 KiB
60Futási hiba3ms2960 KiB
61Futási hiba3ms3236 KiB
62Futási hiba3ms3180 KiB
63Futási hiba3ms3372 KiB
64Elfogadva4ms3496 KiB
65Elfogadva14ms4032 KiB
66Elfogadva14ms4280 KiB
67Elfogadva14ms4344 KiB
68Elfogadva7ms3888 KiB
69Futási hiba4ms4044 KiB
70Futási hiba6ms4560 KiB
71Futási hiba6ms4584 KiB
72Futási hiba7ms4668 KiB
73Elfogadva39ms5072 KiB
74Elfogadva35ms5060 KiB
75Elfogadva37ms5188 KiB
76Elfogadva27ms4900 KiB
77Elfogadva14ms4848 KiB
78Elfogadva8ms4892 KiB
79Futási hiba34ms5572 KiB
80Futási hiba25ms5480 KiB
81Futási hiba25ms5476 KiB
82Hibás válasz14ms5320 KiB
83Elfogadva435ms5264 KiB
84Elfogadva381ms5132 KiB
85Elfogadva425ms5168 KiB
86Elfogadva391ms5420 KiB
87Elfogadva246ms5356 KiB
88Elfogadva430ms5376 KiB
89Elfogadva375ms5372 KiB
90Elfogadva421ms5316 KiB
91Elfogadva388ms5316 KiB
92Elfogadva241ms5288 KiB
93Elfogadva116ms6736 KiB
94Futási hiba28ms6788 KiB
95Futási hiba34ms6916 KiB
96Futási hiba35ms6932 KiB
97Hibás válasz43ms6556 KiB
98Elfogadva104ms7588 KiB
99Elfogadva97ms6332 KiB
100Elfogadva680ms12720 KiB
101Elfogadva711ms12704 KiB
102Elfogadva658ms12640 KiB
103Elfogadva565ms12820 KiB
104Elfogadva430ms12832 KiB
105Elfogadva559ms12688 KiB
106Elfogadva554ms12836 KiB
107Elfogadva540ms12936 KiB
108Elfogadva666ms13020 KiB
109Elfogadva136ms5528 KiB
110Elfogadva370ms8368 KiB
111Elfogadva425ms5744 KiB
112Elfogadva340ms5988 KiB
113Elfogadva361ms5728 KiB
114Futási hiba39ms13136 KiB
115Futási hiba34ms6672 KiB
116Futási hiba35ms6840 KiB
117Futási hiba32ms12828 KiB
118Futási hiba187ms12540 KiB