108082024-04-15 10:30:25AblablablaAutó-tortúracpp17Time limit exceeded 0/1001.601s40020 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][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));
    cout << megold(0, k) << "\n";
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1812 KiB
2Time limit exceeded1.57s20936 KiB
subtask20/12
3Runtime error3ms2376 KiB
4Accepted3ms2408 KiB
5Runtime error3ms2748 KiB
6Runtime error3ms3028 KiB
7Runtime error3ms2976 KiB
8Runtime error3ms3144 KiB
9Runtime error3ms3232 KiB
10Runtime error3ms3144 KiB
subtask30/18
11Runtime error3ms2376 KiB
12Accepted3ms2408 KiB
13Runtime error3ms2748 KiB
14Runtime error3ms3028 KiB
15Runtime error3ms2976 KiB
16Runtime error3ms3144 KiB
17Runtime error3ms3232 KiB
18Runtime error3ms3144 KiB
19Runtime error4ms3348 KiB
20Runtime error23ms4256 KiB
21Accepted28ms4300 KiB
22Runtime error23ms4256 KiB
23Runtime error23ms4256 KiB
24Runtime error23ms4000 KiB
25Runtime error23ms4100 KiB
26Runtime error23ms4212 KiB
27Runtime error23ms4092 KiB
subtask40/25
28Runtime error3ms2376 KiB
29Accepted3ms2408 KiB
30Runtime error3ms2748 KiB
31Runtime error3ms3028 KiB
32Runtime error3ms2976 KiB
33Runtime error3ms3144 KiB
34Runtime error3ms3232 KiB
35Runtime error3ms3144 KiB
36Time limit exceeded1.562s38204 KiB
37Time limit exceeded1.541s38496 KiB
38Time limit exceeded1.567s38476 KiB
39Time limit exceeded1.555s38652 KiB
40Time limit exceeded1.564s38564 KiB
41Time limit exceeded1.555s38620 KiB
42Time limit exceeded1.552s38648 KiB
43Time limit exceeded1.567s38720 KiB
44Time limit exceeded1.57s39056 KiB
45Time limit exceeded1.552s38896 KiB
subtask50/24
46Time limit exceeded1.555s39032 KiB
47Time limit exceeded1.572s38868 KiB
48Time limit exceeded1.536s38880 KiB
49Time limit exceeded1.58s38872 KiB
50Time limit exceeded1.557s39100 KiB
51Time limit exceeded1.574s39332 KiB
52Time limit exceeded1.56s39372 KiB
53Time limit exceeded1.601s39264 KiB
54Time limit exceeded1.582s39240 KiB
55Time limit exceeded1.552s39304 KiB
subtask60/21
56Runtime error3ms2376 KiB
57Accepted3ms2408 KiB
58Runtime error3ms2748 KiB
59Runtime error3ms3028 KiB
60Runtime error3ms2976 KiB
61Runtime error3ms3144 KiB
62Runtime error3ms3232 KiB
63Runtime error3ms3144 KiB
64Runtime error4ms3348 KiB
65Runtime error23ms4256 KiB
66Accepted28ms4300 KiB
67Runtime error23ms4256 KiB
68Runtime error23ms4256 KiB
69Runtime error23ms4000 KiB
70Runtime error23ms4100 KiB
71Runtime error23ms4212 KiB
72Runtime error23ms4092 KiB
73Time limit exceeded1.562s38204 KiB
74Time limit exceeded1.541s38496 KiB
75Time limit exceeded1.567s38476 KiB
76Time limit exceeded1.555s38652 KiB
77Time limit exceeded1.564s38564 KiB
78Time limit exceeded1.555s38620 KiB
79Time limit exceeded1.552s38648 KiB
80Time limit exceeded1.567s38720 KiB
81Time limit exceeded1.57s39056 KiB
82Time limit exceeded1.552s38896 KiB
83Time limit exceeded1.555s39032 KiB
84Time limit exceeded1.572s38868 KiB
85Time limit exceeded1.536s38880 KiB
86Time limit exceeded1.58s38872 KiB
87Time limit exceeded1.557s39100 KiB
88Time limit exceeded1.574s39332 KiB
89Time limit exceeded1.56s39372 KiB
90Time limit exceeded1.601s39264 KiB
91Time limit exceeded1.582s39240 KiB
92Time limit exceeded1.552s39304 KiB
93Time limit exceeded1.572s39312 KiB
94Time limit exceeded1.546s39268 KiB
95Time limit exceeded1.526s39332 KiB
96Time limit exceeded1.562s39520 KiB
97Time limit exceeded1.546s39564 KiB
98Runtime error1.248s16872 KiB
99Time limit exceeded1.577s39504 KiB
100Time limit exceeded1.565s39456 KiB
101Time limit exceeded1.557s39488 KiB
102Time limit exceeded1.549s39492 KiB
103Time limit exceeded1.57s39764 KiB
104Time limit exceeded1.57s39800 KiB
105Time limit exceeded1.58s39804 KiB
106Time limit exceeded1.58s39952 KiB
107Time limit exceeded1.554s39900 KiB
108Time limit exceeded1.56s39764 KiB
109Time limit exceeded1.554s39656 KiB
110Time limit exceeded1.565s39756 KiB
111Time limit exceeded1.572s39828 KiB
112Time limit exceeded1.555s39804 KiB
113Time limit exceeded1.585s39760 KiB
114Time limit exceeded1.57s39952 KiB
115Time limit exceeded1.562s40020 KiB
116Time limit exceeded1.572s39956 KiB
117Time limit exceeded1.555s39960 KiB
118Time limit exceeded1.565s39972 KiB