108292024-04-16 09:17:29AblablablaAutó-tortúracpp17Hibás válasz 24/100728ms13224 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[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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1936 KiB
2Elfogadva351ms7104 KiB
subtask20/12
3Elfogadva3ms2248 KiB
4Elfogadva3ms2460 KiB
5Elfogadva3ms2612 KiB
6Elfogadva3ms2924 KiB
7Elfogadva2ms2868 KiB
8Hibás válasz2ms3004 KiB
9Hibás válasz3ms2868 KiB
10Elfogadva3ms3112 KiB
subtask30/18
11Elfogadva3ms2248 KiB
12Elfogadva3ms2460 KiB
13Elfogadva3ms2612 KiB
14Elfogadva3ms2924 KiB
15Elfogadva2ms2868 KiB
16Hibás válasz2ms3004 KiB
17Hibás válasz3ms2868 KiB
18Elfogadva3ms3112 KiB
19Elfogadva4ms3136 KiB
20Elfogadva16ms3632 KiB
21Elfogadva14ms3940 KiB
22Elfogadva14ms3884 KiB
23Elfogadva8ms3796 KiB
24Hibás válasz6ms3796 KiB
25Hibás válasz14ms4100 KiB
26Hibás válasz12ms4052 KiB
27Hibás válasz7ms4172 KiB
subtask40/25
28Elfogadva3ms2248 KiB
29Elfogadva3ms2460 KiB
30Elfogadva3ms2612 KiB
31Elfogadva3ms2924 KiB
32Elfogadva2ms2868 KiB
33Hibás válasz2ms3004 KiB
34Hibás válasz3ms2868 KiB
35Elfogadva3ms3112 KiB
36Elfogadva39ms4864 KiB
37Elfogadva35ms5088 KiB
38Elfogadva37ms5116 KiB
39Elfogadva27ms4852 KiB
40Elfogadva14ms4676 KiB
41Elfogadva8ms4576 KiB
42Hibás válasz37ms5380 KiB
43Elfogadva28ms5172 KiB
44Hibás válasz28ms5408 KiB
45Hibás válasz14ms5408 KiB
subtask524/24
46Elfogadva435ms5204 KiB
47Elfogadva379ms5184 KiB
48Elfogadva425ms5384 KiB
49Elfogadva393ms5384 KiB
50Elfogadva247ms5336 KiB
51Elfogadva430ms5352 KiB
52Elfogadva375ms5288 KiB
53Elfogadva423ms5332 KiB
54Elfogadva388ms5440 KiB
55Elfogadva243ms5532 KiB
subtask60/21
56Elfogadva3ms2248 KiB
57Elfogadva3ms2460 KiB
58Elfogadva3ms2612 KiB
59Elfogadva3ms2924 KiB
60Elfogadva2ms2868 KiB
61Hibás válasz2ms3004 KiB
62Hibás válasz3ms2868 KiB
63Elfogadva3ms3112 KiB
64Elfogadva4ms3136 KiB
65Elfogadva16ms3632 KiB
66Elfogadva14ms3940 KiB
67Elfogadva14ms3884 KiB
68Elfogadva8ms3796 KiB
69Hibás válasz6ms3796 KiB
70Hibás válasz14ms4100 KiB
71Hibás válasz12ms4052 KiB
72Hibás válasz7ms4172 KiB
73Elfogadva39ms4864 KiB
74Elfogadva35ms5088 KiB
75Elfogadva37ms5116 KiB
76Elfogadva27ms4852 KiB
77Elfogadva14ms4676 KiB
78Elfogadva8ms4576 KiB
79Hibás válasz37ms5380 KiB
80Elfogadva28ms5172 KiB
81Hibás válasz28ms5408 KiB
82Hibás válasz14ms5408 KiB
83Elfogadva435ms5204 KiB
84Elfogadva379ms5184 KiB
85Elfogadva425ms5384 KiB
86Elfogadva393ms5384 KiB
87Elfogadva247ms5336 KiB
88Elfogadva430ms5352 KiB
89Elfogadva375ms5288 KiB
90Elfogadva423ms5332 KiB
91Elfogadva388ms5440 KiB
92Elfogadva243ms5532 KiB
93Elfogadva112ms6784 KiB
94Hibás válasz109ms6784 KiB
95Hibás válasz133ms7016 KiB
96Hibás válasz140ms7016 KiB
97Hibás válasz43ms6568 KiB
98Elfogadva129ms7684 KiB
99Elfogadva97ms6500 KiB
100Elfogadva699ms12972 KiB
101Elfogadva728ms12964 KiB
102Elfogadva679ms13044 KiB
103Elfogadva584ms13088 KiB
104Elfogadva449ms12988 KiB
105Elfogadva578ms12960 KiB
106Elfogadva573ms13096 KiB
107Elfogadva612ms13032 KiB
108Elfogadva689ms13224 KiB
109Elfogadva136ms5668 KiB
110Elfogadva375ms8352 KiB
111Elfogadva425ms5764 KiB
112Elfogadva340ms6028 KiB
113Elfogadva363ms5772 KiB
114Hibás válasz634ms12980 KiB
115Hibás válasz93ms6740 KiB
116Hibás válasz96ms6716 KiB
117Hibás válasz572ms12944 KiB
118Hibás válasz190ms12620 KiB