108102024-04-15 11:08:02AblablablaAutó-tortúracpp17Időlimit túllépés 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";
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1680 KiB
2Időlimit túllépés1.6s20652 KiB
subtask20/12
3Elfogadva3ms2060 KiB
4Hibás válasz3ms2272 KiB
5Elfogadva3ms2512 KiB
6Hibás válasz3ms2620 KiB
7Hibás válasz3ms2820 KiB
8Hibás válasz3ms3076 KiB
9Hibás válasz3ms3196 KiB
10Elfogadva3ms3224 KiB
subtask30/18
11Elfogadva3ms2060 KiB
12Hibás válasz3ms2272 KiB
13Elfogadva3ms2512 KiB
14Hibás válasz3ms2620 KiB
15Hibás válasz3ms2820 KiB
16Hibás válasz3ms3076 KiB
17Hibás válasz3ms3196 KiB
18Elfogadva3ms3224 KiB
19Hibás válasz4ms3548 KiB
20Hibás válasz35ms4608 KiB
21Elfogadva39ms4692 KiB
22Hibás válasz29ms4824 KiB
23Hibás válasz26ms5068 KiB
24Hibás válasz25ms4488 KiB
25Hibás válasz25ms4632 KiB
26Hibás válasz25ms4812 KiB
27Hibás válasz24ms4888 KiB
subtask40/25
28Elfogadva3ms2060 KiB
29Hibás válasz3ms2272 KiB
30Elfogadva3ms2512 KiB
31Hibás válasz3ms2620 KiB
32Hibás válasz3ms2820 KiB
33Hibás válasz3ms3076 KiB
34Hibás válasz3ms3196 KiB
35Elfogadva3ms3224 KiB
36Időlimit túllépés1.552s38996 KiB
37Időlimit túllépés1.577s38976 KiB
38Időlimit túllépés1.559s39300 KiB
39Időlimit túllépés1.574s39340 KiB
40Időlimit túllépés1.569s39208 KiB
41Időlimit túllépés1.569s39208 KiB
42Időlimit túllépés1.555s39208 KiB
43Időlimit túllépés1.555s39172 KiB
44Időlimit túllépés1.577s39440 KiB
45Időlimit túllépés1.564s39340 KiB
subtask50/24
46Időlimit túllépés1.575s39348 KiB
47Időlimit túllépés1.57s39504 KiB
48Időlimit túllépés1.562s39600 KiB
49Időlimit túllépés1.58s39344 KiB
50Időlimit túllépés1.552s39384 KiB
51Időlimit túllépés1.572s39440 KiB
52Időlimit túllépés1.575s39500 KiB
53Időlimit túllépés1.582s39448 KiB
54Időlimit túllépés1.569s39744 KiB
55Időlimit túllépés1.564s39672 KiB
subtask60/21
56Elfogadva3ms2060 KiB
57Hibás válasz3ms2272 KiB
58Elfogadva3ms2512 KiB
59Hibás válasz3ms2620 KiB
60Hibás válasz3ms2820 KiB
61Hibás válasz3ms3076 KiB
62Hibás válasz3ms3196 KiB
63Elfogadva3ms3224 KiB
64Hibás válasz4ms3548 KiB
65Hibás válasz35ms4608 KiB
66Elfogadva39ms4692 KiB
67Hibás válasz29ms4824 KiB
68Hibás válasz26ms5068 KiB
69Hibás válasz25ms4488 KiB
70Hibás válasz25ms4632 KiB
71Hibás válasz25ms4812 KiB
72Hibás válasz24ms4888 KiB
73Időlimit túllépés1.552s38996 KiB
74Időlimit túllépés1.577s38976 KiB
75Időlimit túllépés1.559s39300 KiB
76Időlimit túllépés1.574s39340 KiB
77Időlimit túllépés1.569s39208 KiB
78Időlimit túllépés1.569s39208 KiB
79Időlimit túllépés1.555s39208 KiB
80Időlimit túllépés1.555s39172 KiB
81Időlimit túllépés1.577s39440 KiB
82Időlimit túllépés1.564s39340 KiB
83Időlimit túllépés1.575s39348 KiB
84Időlimit túllépés1.57s39504 KiB
85Időlimit túllépés1.562s39600 KiB
86Időlimit túllépés1.58s39344 KiB
87Időlimit túllépés1.552s39384 KiB
88Időlimit túllépés1.572s39440 KiB
89Időlimit túllépés1.575s39500 KiB
90Időlimit túllépés1.582s39448 KiB
91Időlimit túllépés1.569s39744 KiB
92Időlimit túllépés1.564s39672 KiB
93Időlimit túllépés1.585s39488 KiB
94Időlimit túllépés1.555s39892 KiB
95Időlimit túllépés1.59s39888 KiB
96Időlimit túllépés1.557s39812 KiB
97Időlimit túllépés1.555s39828 KiB
98Időlimit túllépés1.562s8300 KiB
99Időlimit túllépés1.57s40028 KiB
100Időlimit túllépés1.562s39832 KiB
101Időlimit túllépés1.577s39876 KiB
102Időlimit túllépés1.565s39872 KiB
103Időlimit túllépés1.557s39816 KiB
104Időlimit túllépés1.56s39892 KiB
105Időlimit túllépés1.577s39976 KiB
106Időlimit túllépés1.569s39972 KiB
107Időlimit túllépés1.569s39912 KiB
108Időlimit túllépés1.58s40032 KiB
109Időlimit túllépés1.56s39880 KiB
110Időlimit túllépés1.559s39952 KiB
111Időlimit túllépés1.572s40016 KiB
112Időlimit túllépés1.555s39996 KiB
113Időlimit túllépés1.572s39908 KiB
114Időlimit túllépés1.58s39900 KiB
115Időlimit túllépés1.572s39888 KiB
116Időlimit túllépés1.577s39876 KiB
117Időlimit túllépés1.58s40024 KiB
118Időlimit túllépés1.567s39968 KiB