108152024-04-15 14:57:37AblablablaAutó-tortúracpp17Wrong answer 24/100759ms13296 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";
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1960 KiB
2Accepted351ms7384 KiB
subtask20/12
3Accepted3ms2468 KiB
4Accepted2ms2488 KiB
5Accepted3ms2492 KiB
6Accepted3ms2708 KiB
7Accepted3ms2908 KiB
8Wrong answer3ms3120 KiB
9Wrong answer3ms3380 KiB
10Accepted3ms3504 KiB
subtask30/18
11Accepted3ms2468 KiB
12Accepted2ms2488 KiB
13Accepted3ms2492 KiB
14Accepted3ms2708 KiB
15Accepted3ms2908 KiB
16Wrong answer3ms3120 KiB
17Wrong answer3ms3380 KiB
18Accepted3ms3504 KiB
19Accepted4ms3656 KiB
20Accepted16ms4408 KiB
21Accepted14ms4320 KiB
22Accepted14ms4580 KiB
23Accepted7ms4480 KiB
24Wrong answer6ms4608 KiB
25Wrong answer14ms5080 KiB
26Wrong answer12ms5144 KiB
27Wrong answer7ms4908 KiB
subtask40/25
28Accepted3ms2468 KiB
29Accepted2ms2488 KiB
30Accepted3ms2492 KiB
31Accepted3ms2708 KiB
32Accepted3ms2908 KiB
33Wrong answer3ms3120 KiB
34Wrong answer3ms3380 KiB
35Accepted3ms3504 KiB
36Accepted39ms5644 KiB
37Accepted35ms5724 KiB
38Accepted39ms5872 KiB
39Accepted27ms5712 KiB
40Accepted14ms5436 KiB
41Accepted8ms5348 KiB
42Wrong answer37ms5904 KiB
43Accepted28ms6072 KiB
44Wrong answer28ms5996 KiB
45Wrong answer14ms5928 KiB
subtask524/24
46Accepted435ms5788 KiB
47Accepted379ms5916 KiB
48Accepted425ms6096 KiB
49Accepted393ms5964 KiB
50Accepted247ms5880 KiB
51Accepted432ms5768 KiB
52Accepted375ms5752 KiB
53Accepted421ms5916 KiB
54Accepted388ms5800 KiB
55Accepted244ms5668 KiB
subtask60/21
56Accepted3ms2468 KiB
57Accepted2ms2488 KiB
58Accepted3ms2492 KiB
59Accepted3ms2708 KiB
60Accepted3ms2908 KiB
61Wrong answer3ms3120 KiB
62Wrong answer3ms3380 KiB
63Accepted3ms3504 KiB
64Accepted4ms3656 KiB
65Accepted16ms4408 KiB
66Accepted14ms4320 KiB
67Accepted14ms4580 KiB
68Accepted7ms4480 KiB
69Wrong answer6ms4608 KiB
70Wrong answer14ms5080 KiB
71Wrong answer12ms5144 KiB
72Wrong answer7ms4908 KiB
73Accepted39ms5644 KiB
74Accepted35ms5724 KiB
75Accepted39ms5872 KiB
76Accepted27ms5712 KiB
77Accepted14ms5436 KiB
78Accepted8ms5348 KiB
79Wrong answer37ms5904 KiB
80Accepted28ms6072 KiB
81Wrong answer28ms5996 KiB
82Wrong answer14ms5928 KiB
83Accepted435ms5788 KiB
84Accepted379ms5916 KiB
85Accepted425ms6096 KiB
86Accepted393ms5964 KiB
87Accepted247ms5880 KiB
88Accepted432ms5768 KiB
89Accepted375ms5752 KiB
90Accepted421ms5916 KiB
91Accepted388ms5800 KiB
92Accepted244ms5668 KiB
93Accepted112ms7080 KiB
94Wrong answer109ms7220 KiB
95Wrong answer133ms7164 KiB
96Wrong answer140ms7196 KiB
97Wrong answer45ms6964 KiB
98Accepted109ms8228 KiB
99Accepted97ms6964 KiB
100Accepted759ms13296 KiB
101Accepted728ms13080 KiB
102Accepted677ms13020 KiB
103Accepted584ms13072 KiB
104Accepted449ms13180 KiB
105Accepted642ms13152 KiB
106Accepted572ms13148 KiB
107Accepted559ms13080 KiB
108Accepted688ms13080 KiB
109Accepted135ms5776 KiB
110Accepted375ms8504 KiB
111Accepted425ms5976 KiB
112Accepted340ms6104 KiB
113Accepted363ms5704 KiB
114Wrong answer633ms13104 KiB
115Wrong answer94ms6724 KiB
116Wrong answer96ms6648 KiB
117Wrong answer570ms13008 KiB
118Wrong answer192ms12744 KiB