108302024-04-16 09:24:15AblablablaAutó-tortúracpp17Elfogadva 100/100712ms13460 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 o = 0; o < b; o++){
        for(ll i = 0; i < b; i++){
            for(ll j = 0; j < b; j++){
                kutKut[i][j] = min(kutKut[i][j], kutKut[i][o] + kutKut[o][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[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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1812 KiB
2Elfogadva344ms7068 KiB
subtask212/12
3Elfogadva3ms2084 KiB
4Elfogadva3ms2336 KiB
5Elfogadva3ms2576 KiB
6Elfogadva3ms2788 KiB
7Elfogadva3ms2756 KiB
8Elfogadva3ms2852 KiB
9Elfogadva3ms2936 KiB
10Elfogadva3ms3064 KiB
subtask318/18
11Elfogadva3ms2084 KiB
12Elfogadva3ms2336 KiB
13Elfogadva3ms2576 KiB
14Elfogadva3ms2788 KiB
15Elfogadva3ms2756 KiB
16Elfogadva3ms2852 KiB
17Elfogadva3ms2936 KiB
18Elfogadva3ms3064 KiB
19Elfogadva4ms3480 KiB
20Elfogadva14ms3928 KiB
21Elfogadva14ms4248 KiB
22Elfogadva14ms4452 KiB
23Elfogadva7ms4168 KiB
24Elfogadva6ms4104 KiB
25Elfogadva14ms4568 KiB
26Elfogadva12ms4544 KiB
27Elfogadva7ms4468 KiB
subtask425/25
28Elfogadva3ms2084 KiB
29Elfogadva3ms2336 KiB
30Elfogadva3ms2576 KiB
31Elfogadva3ms2788 KiB
32Elfogadva3ms2756 KiB
33Elfogadva3ms2852 KiB
34Elfogadva3ms2936 KiB
35Elfogadva3ms3064 KiB
36Elfogadva39ms4928 KiB
37Elfogadva35ms4912 KiB
38Elfogadva37ms5040 KiB
39Elfogadva27ms4800 KiB
40Elfogadva14ms4748 KiB
41Elfogadva8ms4804 KiB
42Elfogadva37ms5564 KiB
43Elfogadva28ms5480 KiB
44Elfogadva28ms5444 KiB
45Elfogadva14ms5136 KiB
subtask524/24
46Elfogadva439ms5308 KiB
47Elfogadva386ms5296 KiB
48Elfogadva430ms5284 KiB
49Elfogadva400ms5536 KiB
50Elfogadva241ms5388 KiB
51Elfogadva435ms5404 KiB
52Elfogadva382ms5344 KiB
53Elfogadva425ms5360 KiB
54Elfogadva395ms5372 KiB
55Elfogadva237ms5352 KiB
subtask621/21
56Elfogadva3ms2084 KiB
57Elfogadva3ms2336 KiB
58Elfogadva3ms2576 KiB
59Elfogadva3ms2788 KiB
60Elfogadva3ms2756 KiB
61Elfogadva3ms2852 KiB
62Elfogadva3ms2936 KiB
63Elfogadva3ms3064 KiB
64Elfogadva4ms3480 KiB
65Elfogadva14ms3928 KiB
66Elfogadva14ms4248 KiB
67Elfogadva14ms4452 KiB
68Elfogadva7ms4168 KiB
69Elfogadva6ms4104 KiB
70Elfogadva14ms4568 KiB
71Elfogadva12ms4544 KiB
72Elfogadva7ms4468 KiB
73Elfogadva39ms4928 KiB
74Elfogadva35ms4912 KiB
75Elfogadva37ms5040 KiB
76Elfogadva27ms4800 KiB
77Elfogadva14ms4748 KiB
78Elfogadva8ms4804 KiB
79Elfogadva37ms5564 KiB
80Elfogadva28ms5480 KiB
81Elfogadva28ms5444 KiB
82Elfogadva14ms5136 KiB
83Elfogadva439ms5308 KiB
84Elfogadva386ms5296 KiB
85Elfogadva430ms5284 KiB
86Elfogadva400ms5536 KiB
87Elfogadva241ms5388 KiB
88Elfogadva435ms5404 KiB
89Elfogadva382ms5344 KiB
90Elfogadva425ms5360 KiB
91Elfogadva395ms5372 KiB
92Elfogadva237ms5352 KiB
93Elfogadva111ms6772 KiB
94Elfogadva108ms6908 KiB
95Elfogadva145ms7352 KiB
96Elfogadva137ms7212 KiB
97Elfogadva43ms6988 KiB
98Elfogadva104ms8116 KiB
99Elfogadva96ms6768 KiB
100Elfogadva680ms13364 KiB
101Elfogadva712ms13460 KiB
102Elfogadva657ms13252 KiB
103Elfogadva574ms13132 KiB
104Elfogadva435ms13080 KiB
105Elfogadva565ms13124 KiB
106Elfogadva560ms13052 KiB
107Elfogadva551ms13148 KiB
108Elfogadva674ms13148 KiB
109Elfogadva136ms5692 KiB
110Elfogadva379ms8540 KiB
111Elfogadva437ms5964 KiB
112Elfogadva349ms6220 KiB
113Elfogadva374ms5920 KiB
114Elfogadva625ms13328 KiB
115Elfogadva93ms6912 KiB
116Elfogadva93ms6832 KiB
117Elfogadva523ms12960 KiB
118Elfogadva187ms12640 KiB