108072024-04-15 10:27:30AblablablaAutó-tortúracpp17Time limit exceeded 0/1001.585s76388 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 = megold(ind + 1, tank - tav[latogat[ind]][latogat[ind + 1]]) + tav[latogat[ind]][latogat[ind + 1]];

    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 = megold(ind + 1, k - mini) + tav[latogat[ind]][minInd] + tav[minInd][latogat[ind + 1]];

    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++){
                tav[i][j] = min(tav[i][j], tav[i][k] + tav[k][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));
    cout << megold(0, k) << "\n";
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1812 KiB
2Time limit exceeded1.555s20924 KiB
subtask20/12
3Runtime error3ms2728 KiB
4Runtime error3ms2644 KiB
5Runtime error3ms2848 KiB
6Runtime error3ms3052 KiB
7Wrong answer2ms2956 KiB
8Wrong answer3ms3064 KiB
9Runtime error3ms3288 KiB
10Wrong answer3ms3168 KiB
subtask30/18
11Runtime error3ms2728 KiB
12Runtime error3ms2644 KiB
13Runtime error3ms2848 KiB
14Runtime error3ms3052 KiB
15Wrong answer2ms2956 KiB
16Wrong answer3ms3064 KiB
17Runtime error3ms3288 KiB
18Wrong answer3ms3168 KiB
19Runtime error4ms3576 KiB
20Runtime error3ms4044 KiB
21Runtime error3ms4260 KiB
22Runtime error3ms4520 KiB
23Runtime error3ms4728 KiB
24Runtime error30ms4692 KiB
25Runtime error30ms4792 KiB
26Runtime error30ms4904 KiB
27Runtime error29ms4904 KiB
subtask40/25
28Runtime error3ms2728 KiB
29Runtime error3ms2644 KiB
30Runtime error3ms2848 KiB
31Runtime error3ms3052 KiB
32Wrong answer2ms2956 KiB
33Wrong answer3ms3064 KiB
34Runtime error3ms3288 KiB
35Wrong answer3ms3168 KiB
36Time limit exceeded1.57s39024 KiB
37Time limit exceeded1.526s39140 KiB
38Time limit exceeded1.585s39288 KiB
39Time limit exceeded1.537s39396 KiB
40Time limit exceeded1.58s39356 KiB
41Time limit exceeded1.57s39440 KiB
42Time limit exceeded1.565s39636 KiB
43Time limit exceeded1.575s39592 KiB
44Time limit exceeded1.564s39656 KiB
45Time limit exceeded1.57s39788 KiB
subtask50/24
46Time limit exceeded1.577s39724 KiB
47Time limit exceeded1.542s39664 KiB
48Time limit exceeded1.57s39620 KiB
49Time limit exceeded1.577s39596 KiB
50Time limit exceeded1.565s39588 KiB
51Time limit exceeded1.562s39700 KiB
52Time limit exceeded1.56s39748 KiB
53Time limit exceeded1.574s39700 KiB
54Time limit exceeded1.569s39648 KiB
55Time limit exceeded1.562s39580 KiB
subtask60/21
56Runtime error3ms2728 KiB
57Runtime error3ms2644 KiB
58Runtime error3ms2848 KiB
59Runtime error3ms3052 KiB
60Wrong answer2ms2956 KiB
61Wrong answer3ms3064 KiB
62Runtime error3ms3288 KiB
63Wrong answer3ms3168 KiB
64Runtime error4ms3576 KiB
65Runtime error3ms4044 KiB
66Runtime error3ms4260 KiB
67Runtime error3ms4520 KiB
68Runtime error3ms4728 KiB
69Runtime error30ms4692 KiB
70Runtime error30ms4792 KiB
71Runtime error30ms4904 KiB
72Runtime error29ms4904 KiB
73Time limit exceeded1.57s39024 KiB
74Time limit exceeded1.526s39140 KiB
75Time limit exceeded1.585s39288 KiB
76Time limit exceeded1.537s39396 KiB
77Time limit exceeded1.58s39356 KiB
78Time limit exceeded1.57s39440 KiB
79Time limit exceeded1.565s39636 KiB
80Time limit exceeded1.575s39592 KiB
81Time limit exceeded1.564s39656 KiB
82Time limit exceeded1.57s39788 KiB
83Time limit exceeded1.577s39724 KiB
84Time limit exceeded1.542s39664 KiB
85Time limit exceeded1.57s39620 KiB
86Time limit exceeded1.577s39596 KiB
87Time limit exceeded1.565s39588 KiB
88Time limit exceeded1.562s39700 KiB
89Time limit exceeded1.56s39748 KiB
90Time limit exceeded1.574s39700 KiB
91Time limit exceeded1.569s39648 KiB
92Time limit exceeded1.562s39580 KiB
93Time limit exceeded1.577s39756 KiB
94Time limit exceeded1.585s39868 KiB
95Time limit exceeded1.57s39892 KiB
96Time limit exceeded1.57s39880 KiB
97Time limit exceeded1.577s39804 KiB
98Time limit exceeded1.559s8380 KiB
99Time limit exceeded1.57s39688 KiB
100Time limit exceeded1.562s39620 KiB
101Runtime error39ms76024 KiB
102Time limit exceeded1.554s39744 KiB
103Runtime error35ms76044 KiB
104Runtime error35ms75948 KiB
105Runtime error29ms76028 KiB
106Runtime error35ms76144 KiB
107Runtime error37ms76028 KiB
108Runtime error39ms76060 KiB
109Runtime error35ms75936 KiB
110Runtime error30ms76024 KiB
111Runtime error39ms76224 KiB
112Runtime error37ms76268 KiB
113Runtime error37ms76388 KiB
114Time limit exceeded1.57s39976 KiB
115Time limit exceeded1.562s39892 KiB
116Time limit exceeded1.565s39880 KiB
117Time limit exceeded1.557s39960 KiB
118Time limit exceeded1.572s39964 KiB