108102024-04-15 11:08:02AblablablaAutó-tortúracpp17Time limit exceeded 0/1001.6s40032 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]]) : 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) + k - (tank - tav[latogat[ind]][minInd]) : 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) + k;
    if(a >= INF){
        cout << "-1\n";
    } else{
        cout << a << "\n";
    }
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1680 KiB
2Time limit exceeded1.6s20652 KiB
subtask20/12
3Accepted3ms2060 KiB
4Wrong answer3ms2272 KiB
5Accepted3ms2512 KiB
6Wrong answer3ms2620 KiB
7Wrong answer3ms2820 KiB
8Wrong answer3ms3076 KiB
9Wrong answer3ms3196 KiB
10Accepted3ms3224 KiB
subtask30/18
11Accepted3ms2060 KiB
12Wrong answer3ms2272 KiB
13Accepted3ms2512 KiB
14Wrong answer3ms2620 KiB
15Wrong answer3ms2820 KiB
16Wrong answer3ms3076 KiB
17Wrong answer3ms3196 KiB
18Accepted3ms3224 KiB
19Wrong answer4ms3548 KiB
20Wrong answer35ms4608 KiB
21Accepted39ms4692 KiB
22Wrong answer29ms4824 KiB
23Wrong answer26ms5068 KiB
24Wrong answer25ms4488 KiB
25Wrong answer25ms4632 KiB
26Wrong answer25ms4812 KiB
27Wrong answer24ms4888 KiB
subtask40/25
28Accepted3ms2060 KiB
29Wrong answer3ms2272 KiB
30Accepted3ms2512 KiB
31Wrong answer3ms2620 KiB
32Wrong answer3ms2820 KiB
33Wrong answer3ms3076 KiB
34Wrong answer3ms3196 KiB
35Accepted3ms3224 KiB
36Time limit exceeded1.552s38996 KiB
37Time limit exceeded1.577s38976 KiB
38Time limit exceeded1.559s39300 KiB
39Time limit exceeded1.574s39340 KiB
40Time limit exceeded1.569s39208 KiB
41Time limit exceeded1.569s39208 KiB
42Time limit exceeded1.555s39208 KiB
43Time limit exceeded1.555s39172 KiB
44Time limit exceeded1.577s39440 KiB
45Time limit exceeded1.564s39340 KiB
subtask50/24
46Time limit exceeded1.575s39348 KiB
47Time limit exceeded1.57s39504 KiB
48Time limit exceeded1.562s39600 KiB
49Time limit exceeded1.58s39344 KiB
50Time limit exceeded1.552s39384 KiB
51Time limit exceeded1.572s39440 KiB
52Time limit exceeded1.575s39500 KiB
53Time limit exceeded1.582s39448 KiB
54Time limit exceeded1.569s39744 KiB
55Time limit exceeded1.564s39672 KiB
subtask60/21
56Accepted3ms2060 KiB
57Wrong answer3ms2272 KiB
58Accepted3ms2512 KiB
59Wrong answer3ms2620 KiB
60Wrong answer3ms2820 KiB
61Wrong answer3ms3076 KiB
62Wrong answer3ms3196 KiB
63Accepted3ms3224 KiB
64Wrong answer4ms3548 KiB
65Wrong answer35ms4608 KiB
66Accepted39ms4692 KiB
67Wrong answer29ms4824 KiB
68Wrong answer26ms5068 KiB
69Wrong answer25ms4488 KiB
70Wrong answer25ms4632 KiB
71Wrong answer25ms4812 KiB
72Wrong answer24ms4888 KiB
73Time limit exceeded1.552s38996 KiB
74Time limit exceeded1.577s38976 KiB
75Time limit exceeded1.559s39300 KiB
76Time limit exceeded1.574s39340 KiB
77Time limit exceeded1.569s39208 KiB
78Time limit exceeded1.569s39208 KiB
79Time limit exceeded1.555s39208 KiB
80Time limit exceeded1.555s39172 KiB
81Time limit exceeded1.577s39440 KiB
82Time limit exceeded1.564s39340 KiB
83Time limit exceeded1.575s39348 KiB
84Time limit exceeded1.57s39504 KiB
85Time limit exceeded1.562s39600 KiB
86Time limit exceeded1.58s39344 KiB
87Time limit exceeded1.552s39384 KiB
88Time limit exceeded1.572s39440 KiB
89Time limit exceeded1.575s39500 KiB
90Time limit exceeded1.582s39448 KiB
91Time limit exceeded1.569s39744 KiB
92Time limit exceeded1.564s39672 KiB
93Time limit exceeded1.585s39488 KiB
94Time limit exceeded1.555s39892 KiB
95Time limit exceeded1.59s39888 KiB
96Time limit exceeded1.557s39812 KiB
97Time limit exceeded1.555s39828 KiB
98Time limit exceeded1.562s8300 KiB
99Time limit exceeded1.57s40028 KiB
100Time limit exceeded1.562s39832 KiB
101Time limit exceeded1.577s39876 KiB
102Time limit exceeded1.565s39872 KiB
103Time limit exceeded1.557s39816 KiB
104Time limit exceeded1.56s39892 KiB
105Time limit exceeded1.577s39976 KiB
106Time limit exceeded1.569s39972 KiB
107Time limit exceeded1.569s39912 KiB
108Time limit exceeded1.58s40032 KiB
109Time limit exceeded1.56s39880 KiB
110Time limit exceeded1.559s39952 KiB
111Time limit exceeded1.572s40016 KiB
112Time limit exceeded1.555s39996 KiB
113Time limit exceeded1.572s39908 KiB
114Time limit exceeded1.58s39900 KiB
115Time limit exceeded1.572s39888 KiB
116Time limit exceeded1.577s39876 KiB
117Time limit exceeded1.58s40024 KiB
118Time limit exceeded1.567s39968 KiB