108152024-04-15 14:57:37AblablablaAutó-tortúracpp17Hibás válasz 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";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1960 KiB
2Elfogadva351ms7384 KiB
subtask20/12
3Elfogadva3ms2468 KiB
4Elfogadva2ms2488 KiB
5Elfogadva3ms2492 KiB
6Elfogadva3ms2708 KiB
7Elfogadva3ms2908 KiB
8Hibás válasz3ms3120 KiB
9Hibás válasz3ms3380 KiB
10Elfogadva3ms3504 KiB
subtask30/18
11Elfogadva3ms2468 KiB
12Elfogadva2ms2488 KiB
13Elfogadva3ms2492 KiB
14Elfogadva3ms2708 KiB
15Elfogadva3ms2908 KiB
16Hibás válasz3ms3120 KiB
17Hibás válasz3ms3380 KiB
18Elfogadva3ms3504 KiB
19Elfogadva4ms3656 KiB
20Elfogadva16ms4408 KiB
21Elfogadva14ms4320 KiB
22Elfogadva14ms4580 KiB
23Elfogadva7ms4480 KiB
24Hibás válasz6ms4608 KiB
25Hibás válasz14ms5080 KiB
26Hibás válasz12ms5144 KiB
27Hibás válasz7ms4908 KiB
subtask40/25
28Elfogadva3ms2468 KiB
29Elfogadva2ms2488 KiB
30Elfogadva3ms2492 KiB
31Elfogadva3ms2708 KiB
32Elfogadva3ms2908 KiB
33Hibás válasz3ms3120 KiB
34Hibás válasz3ms3380 KiB
35Elfogadva3ms3504 KiB
36Elfogadva39ms5644 KiB
37Elfogadva35ms5724 KiB
38Elfogadva39ms5872 KiB
39Elfogadva27ms5712 KiB
40Elfogadva14ms5436 KiB
41Elfogadva8ms5348 KiB
42Hibás válasz37ms5904 KiB
43Elfogadva28ms6072 KiB
44Hibás válasz28ms5996 KiB
45Hibás válasz14ms5928 KiB
subtask524/24
46Elfogadva435ms5788 KiB
47Elfogadva379ms5916 KiB
48Elfogadva425ms6096 KiB
49Elfogadva393ms5964 KiB
50Elfogadva247ms5880 KiB
51Elfogadva432ms5768 KiB
52Elfogadva375ms5752 KiB
53Elfogadva421ms5916 KiB
54Elfogadva388ms5800 KiB
55Elfogadva244ms5668 KiB
subtask60/21
56Elfogadva3ms2468 KiB
57Elfogadva2ms2488 KiB
58Elfogadva3ms2492 KiB
59Elfogadva3ms2708 KiB
60Elfogadva3ms2908 KiB
61Hibás válasz3ms3120 KiB
62Hibás válasz3ms3380 KiB
63Elfogadva3ms3504 KiB
64Elfogadva4ms3656 KiB
65Elfogadva16ms4408 KiB
66Elfogadva14ms4320 KiB
67Elfogadva14ms4580 KiB
68Elfogadva7ms4480 KiB
69Hibás válasz6ms4608 KiB
70Hibás válasz14ms5080 KiB
71Hibás válasz12ms5144 KiB
72Hibás válasz7ms4908 KiB
73Elfogadva39ms5644 KiB
74Elfogadva35ms5724 KiB
75Elfogadva39ms5872 KiB
76Elfogadva27ms5712 KiB
77Elfogadva14ms5436 KiB
78Elfogadva8ms5348 KiB
79Hibás válasz37ms5904 KiB
80Elfogadva28ms6072 KiB
81Hibás válasz28ms5996 KiB
82Hibás válasz14ms5928 KiB
83Elfogadva435ms5788 KiB
84Elfogadva379ms5916 KiB
85Elfogadva425ms6096 KiB
86Elfogadva393ms5964 KiB
87Elfogadva247ms5880 KiB
88Elfogadva432ms5768 KiB
89Elfogadva375ms5752 KiB
90Elfogadva421ms5916 KiB
91Elfogadva388ms5800 KiB
92Elfogadva244ms5668 KiB
93Elfogadva112ms7080 KiB
94Hibás válasz109ms7220 KiB
95Hibás válasz133ms7164 KiB
96Hibás válasz140ms7196 KiB
97Hibás válasz45ms6964 KiB
98Elfogadva109ms8228 KiB
99Elfogadva97ms6964 KiB
100Elfogadva759ms13296 KiB
101Elfogadva728ms13080 KiB
102Elfogadva677ms13020 KiB
103Elfogadva584ms13072 KiB
104Elfogadva449ms13180 KiB
105Elfogadva642ms13152 KiB
106Elfogadva572ms13148 KiB
107Elfogadva559ms13080 KiB
108Elfogadva688ms13080 KiB
109Elfogadva135ms5776 KiB
110Elfogadva375ms8504 KiB
111Elfogadva425ms5976 KiB
112Elfogadva340ms6104 KiB
113Elfogadva363ms5704 KiB
114Hibás válasz633ms13104 KiB
115Hibás válasz94ms6724 KiB
116Hibás válasz96ms6648 KiB
117Hibás válasz570ms13008 KiB
118Hibás válasz192ms12744 KiB