108092024-04-15 10:49:35AblablablaAutó-tortúracpp17Time limit exceeded 0/1001.601s40132 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";
    }
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1812 KiB
2Time limit exceeded1.6s20904 KiB
subtask20/12
3Wrong answer3ms2496 KiB
4Accepted3ms2448 KiB
5Accepted2ms2460 KiB
6Accepted3ms2464 KiB
7Accepted3ms2796 KiB
8Wrong answer3ms2836 KiB
9Wrong answer3ms2956 KiB
10Wrong answer3ms3108 KiB
subtask30/18
11Wrong answer3ms2496 KiB
12Accepted3ms2448 KiB
13Accepted2ms2460 KiB
14Accepted3ms2464 KiB
15Accepted3ms2796 KiB
16Wrong answer3ms2836 KiB
17Wrong answer3ms2956 KiB
18Wrong answer3ms3108 KiB
19Accepted4ms3508 KiB
20Accepted35ms4568 KiB
21Accepted39ms4428 KiB
22Accepted28ms4780 KiB
23Accepted27ms4856 KiB
24Wrong answer26ms4144 KiB
25Wrong answer25ms4376 KiB
26Wrong answer25ms4572 KiB
27Wrong answer24ms4584 KiB
subtask40/25
28Wrong answer3ms2496 KiB
29Accepted3ms2448 KiB
30Accepted2ms2460 KiB
31Accepted3ms2464 KiB
32Accepted3ms2796 KiB
33Wrong answer3ms2836 KiB
34Wrong answer3ms2956 KiB
35Wrong answer3ms3108 KiB
36Time limit exceeded1.552s39044 KiB
37Time limit exceeded1.56s39336 KiB
38Time limit exceeded1.574s39392 KiB
39Time limit exceeded1.58s39484 KiB
40Time limit exceeded1.569s39436 KiB
41Time limit exceeded1.567s39480 KiB
42Time limit exceeded1.585s39664 KiB
43Time limit exceeded1.549s39692 KiB
44Time limit exceeded1.56s39688 KiB
45Time limit exceeded1.575s39824 KiB
subtask50/24
46Time limit exceeded1.58s39712 KiB
47Time limit exceeded1.564s39612 KiB
48Time limit exceeded1.516s39616 KiB
49Time limit exceeded1.559s39652 KiB
50Time limit exceeded1.552s39576 KiB
51Time limit exceeded1.542s39944 KiB
52Time limit exceeded1.564s39820 KiB
53Time limit exceeded1.574s39868 KiB
54Time limit exceeded1.564s39804 KiB
55Time limit exceeded1.554s39792 KiB
subtask60/21
56Wrong answer3ms2496 KiB
57Accepted3ms2448 KiB
58Accepted2ms2460 KiB
59Accepted3ms2464 KiB
60Accepted3ms2796 KiB
61Wrong answer3ms2836 KiB
62Wrong answer3ms2956 KiB
63Wrong answer3ms3108 KiB
64Accepted4ms3508 KiB
65Accepted35ms4568 KiB
66Accepted39ms4428 KiB
67Accepted28ms4780 KiB
68Accepted27ms4856 KiB
69Wrong answer26ms4144 KiB
70Wrong answer25ms4376 KiB
71Wrong answer25ms4572 KiB
72Wrong answer24ms4584 KiB
73Time limit exceeded1.552s39044 KiB
74Time limit exceeded1.56s39336 KiB
75Time limit exceeded1.574s39392 KiB
76Time limit exceeded1.58s39484 KiB
77Time limit exceeded1.569s39436 KiB
78Time limit exceeded1.567s39480 KiB
79Time limit exceeded1.585s39664 KiB
80Time limit exceeded1.549s39692 KiB
81Time limit exceeded1.56s39688 KiB
82Time limit exceeded1.575s39824 KiB
83Time limit exceeded1.58s39712 KiB
84Time limit exceeded1.564s39612 KiB
85Time limit exceeded1.516s39616 KiB
86Time limit exceeded1.559s39652 KiB
87Time limit exceeded1.552s39576 KiB
88Time limit exceeded1.542s39944 KiB
89Time limit exceeded1.564s39820 KiB
90Time limit exceeded1.574s39868 KiB
91Time limit exceeded1.564s39804 KiB
92Time limit exceeded1.554s39792 KiB
93Time limit exceeded1.601s39824 KiB
94Time limit exceeded1.575s39760 KiB
95Time limit exceeded1.544s39888 KiB
96Time limit exceeded1.567s39944 KiB
97Time limit exceeded1.575s40036 KiB
98Time limit exceeded1.562s8516 KiB
99Time limit exceeded1.564s39976 KiB
100Time limit exceeded1.562s39992 KiB
101Time limit exceeded1.559s39940 KiB
102Time limit exceeded1.574s39924 KiB
103Time limit exceeded1.585s39820 KiB
104Time limit exceeded1.57s40016 KiB
105Time limit exceeded1.555s40008 KiB
106Time limit exceeded1.56s39972 KiB
107Time limit exceeded1.565s40040 KiB
108Time limit exceeded1.569s39968 KiB
109Time limit exceeded1.565s40132 KiB
110Time limit exceeded1.544s39920 KiB
111Time limit exceeded1.575s40064 KiB
112Time limit exceeded1.547s39856 KiB
113Time limit exceeded1.575s39932 KiB
114Time limit exceeded1.567s39936 KiB
115Time limit exceeded1.559s39944 KiB
116Time limit exceeded1.572s39868 KiB
117Time limit exceeded1.57s39924 KiB
118Time limit exceeded1.555s39964 KiB