10809 2024. 04. 15 10:49:35 Ablablabla Autó-tortúra cpp17 Időlimit túllépés 0/100 1.601s 40132 KiB 
#include <bits/stdc++.h>

using namespace std;

const int INF = 2e9 + 7;

vector<vector<int>> tav;
vector<int> latogat;
int n, m, k, l, b;
vector<int> kut;
vector<vector<int>> dp;

int megold(int ind, int tank){
    if(ind == l - 1){
        if(tank < 0){
            return INF;
        }

        return 0;
    } else if(tank <= 0){
        return INF;
    } else if(dp[ind][tank] != -1){
        return dp[ind][tank];
    }

    int a = (tav[latogat[ind]][latogat[ind + 1]] <= tank ? megold(ind + 1, tank - tav[latogat[ind]][latogat[ind + 1]]) + tav[latogat[ind]][latogat[ind + 1]] : INF);

    int mini = INF;
    int minInd = 0;
    for(int i = 0; i < b; i++){
        if(tav[latogat[ind]][kut[i]] > tank) continue;

        int akt = tav[kut[i]][latogat[ind + 1]];
        if(mini > akt){
            mini = akt;
            minInd = kut[i];
        }
    }

    int b = (mini != INF ? megold(ind + 1, k - mini) + tav[latogat[ind]][minInd] + tav[minInd][latogat[ind + 1]] : INF);

    return dp[ind][tank] = min(a, b);
}

int main()
{
    cin >> n >> m >> k;

    vector<vector<int>> csucsok(n, vector<int>());
    tav.assign(n, vector<int>(n, INF));
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;

        csucsok[a].push_back(b);
        csucsok[b].push_back(a);
        tav[a][b] = 1;
        tav[b][a] = 1;
    }

    for(int i = 0; i < n; i++){
        tav[i][i] = 0;
    }

    for(int l = 0; l < n; l++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(tav[i][l] == INF || tav[l][j] == INF) continue;
                tav[i][j] = min(tav[i][j], tav[i][l] + tav[l][j]);
            }
        }
    }

    cin >> l;
    latogat.assign(l, 0);
    for(int &x : latogat){
        cin >> x;
        x--;
    }

    cin >> b;
    kut.assign(b, 0);
    for(int &x : kut){
        cin >> x;
        x--;
    }

    dp.assign(l, vector<int>(k + 1, -1));
    int a = megold(0, k);
    if(a == INF){
        cout << "-1\n";
    } else{
        cout << a << "\n";
    }
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1812 KiB
2 Időlimit túllépés 1.6s 20904 KiB
subtask2 0/12
3 Hibás válasz 3ms 2496 KiB
4 Elfogadva 3ms 2448 KiB
5 Elfogadva 2ms 2460 KiB
6 Elfogadva 3ms 2464 KiB
7 Elfogadva 3ms 2796 KiB
8 Hibás válasz 3ms 2836 KiB
9 Hibás válasz 3ms 2956 KiB
10 Hibás válasz 3ms 3108 KiB
subtask3 0/18
11 Hibás válasz 3ms 2496 KiB
12 Elfogadva 3ms 2448 KiB
13 Elfogadva 2ms 2460 KiB
14 Elfogadva 3ms 2464 KiB
15 Elfogadva 3ms 2796 KiB
16 Hibás válasz 3ms 2836 KiB
17 Hibás válasz 3ms 2956 KiB
18 Hibás válasz 3ms 3108 KiB
19 Elfogadva 4ms 3508 KiB
20 Elfogadva 35ms 4568 KiB
21 Elfogadva 39ms 4428 KiB
22 Elfogadva 28ms 4780 KiB
23 Elfogadva 27ms 4856 KiB
24 Hibás válasz 26ms 4144 KiB
25 Hibás válasz 25ms 4376 KiB
26 Hibás válasz 25ms 4572 KiB
27 Hibás válasz 24ms 4584 KiB
subtask4 0/25
28 Hibás válasz 3ms 2496 KiB
29 Elfogadva 3ms 2448 KiB
30 Elfogadva 2ms 2460 KiB
31 Elfogadva 3ms 2464 KiB
32 Elfogadva 3ms 2796 KiB
33 Hibás válasz 3ms 2836 KiB
34 Hibás válasz 3ms 2956 KiB
35 Hibás válasz 3ms 3108 KiB
36 Időlimit túllépés 1.552s 39044 KiB
37 Időlimit túllépés 1.56s 39336 KiB
38 Időlimit túllépés 1.574s 39392 KiB
39 Időlimit túllépés 1.58s 39484 KiB
40 Időlimit túllépés 1.569s 39436 KiB
41 Időlimit túllépés 1.567s 39480 KiB
42 Időlimit túllépés 1.585s 39664 KiB
43 Időlimit túllépés 1.549s 39692 KiB
44 Időlimit túllépés 1.56s 39688 KiB
45 Időlimit túllépés 1.575s 39824 KiB
subtask5 0/24
46 Időlimit túllépés 1.58s 39712 KiB
47 Időlimit túllépés 1.564s 39612 KiB
48 Időlimit túllépés 1.516s 39616 KiB
49 Időlimit túllépés 1.559s 39652 KiB
50 Időlimit túllépés 1.552s 39576 KiB
51 Időlimit túllépés 1.542s 39944 KiB
52 Időlimit túllépés 1.564s 39820 KiB
53 Időlimit túllépés 1.574s 39868 KiB
54 Időlimit túllépés 1.564s 39804 KiB
55 Időlimit túllépés 1.554s 39792 KiB
subtask6 0/21
56 Hibás válasz 3ms 2496 KiB
57 Elfogadva 3ms 2448 KiB
58 Elfogadva 2ms 2460 KiB
59 Elfogadva 3ms 2464 KiB
60 Elfogadva 3ms 2796 KiB
61 Hibás válasz 3ms 2836 KiB
62 Hibás válasz 3ms 2956 KiB
63 Hibás válasz 3ms 3108 KiB
64 Elfogadva 4ms 3508 KiB
65 Elfogadva 35ms 4568 KiB
66 Elfogadva 39ms 4428 KiB
67 Elfogadva 28ms 4780 KiB
68 Elfogadva 27ms 4856 KiB
69 Hibás válasz 26ms 4144 KiB
70 Hibás válasz 25ms 4376 KiB
71 Hibás válasz 25ms 4572 KiB
72 Hibás válasz 24ms 4584 KiB
73 Időlimit túllépés 1.552s 39044 KiB
74 Időlimit túllépés 1.56s 39336 KiB
75 Időlimit túllépés 1.574s 39392 KiB
76 Időlimit túllépés 1.58s 39484 KiB
77 Időlimit túllépés 1.569s 39436 KiB
78 Időlimit túllépés 1.567s 39480 KiB
79 Időlimit túllépés 1.585s 39664 KiB
80 Időlimit túllépés 1.549s 39692 KiB
81 Időlimit túllépés 1.56s 39688 KiB
82 Időlimit túllépés 1.575s 39824 KiB
83 Időlimit túllépés 1.58s 39712 KiB
84 Időlimit túllépés 1.564s 39612 KiB
85 Időlimit túllépés 1.516s 39616 KiB
86 Időlimit túllépés 1.559s 39652 KiB
87 Időlimit túllépés 1.552s 39576 KiB
88 Időlimit túllépés 1.542s 39944 KiB
89 Időlimit túllépés 1.564s 39820 KiB
90 Időlimit túllépés 1.574s 39868 KiB
91 Időlimit túllépés 1.564s 39804 KiB
92 Időlimit túllépés 1.554s 39792 KiB
93 Időlimit túllépés 1.601s 39824 KiB
94 Időlimit túllépés 1.575s 39760 KiB
95 Időlimit túllépés 1.544s 39888 KiB
96 Időlimit túllépés 1.567s 39944 KiB
97 Időlimit túllépés 1.575s 40036 KiB
98 Időlimit túllépés 1.562s 8516 KiB
99 Időlimit túllépés 1.564s 39976 KiB
100 Időlimit túllépés 1.562s 39992 KiB
101 Időlimit túllépés 1.559s 39940 KiB
102 Időlimit túllépés 1.574s 39924 KiB
103 Időlimit túllépés 1.585s 39820 KiB
104 Időlimit túllépés 1.57s 40016 KiB
105 Időlimit túllépés 1.555s 40008 KiB
106 Időlimit túllépés 1.56s 39972 KiB
107 Időlimit túllépés 1.565s 40040 KiB
108 Időlimit túllépés 1.569s 39968 KiB
109 Időlimit túllépés 1.565s 40132 KiB
110 Időlimit túllépés 1.544s 39920 KiB
111 Időlimit túllépés 1.575s 40064 KiB
112 Időlimit túllépés 1.547s 39856 KiB
113 Időlimit túllépés 1.575s 39932 KiB
114 Időlimit túllépés 1.567s 39936 KiB
115 Időlimit túllépés 1.559s 39944 KiB
116 Időlimit túllépés 1.572s 39868 KiB
117 Időlimit túllépés 1.57s 39924 KiB
118 Időlimit túllépés 1.555s 39964 KiB