108092024-04-15 10:49:35AblablablaAutó-tortúracpp17Időlimit túllépés 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";
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1812 KiB
2Időlimit túllépés1.6s20904 KiB
subtask20/12
3Hibás válasz3ms2496 KiB
4Elfogadva3ms2448 KiB
5Elfogadva2ms2460 KiB
6Elfogadva3ms2464 KiB
7Elfogadva3ms2796 KiB
8Hibás válasz3ms2836 KiB
9Hibás válasz3ms2956 KiB
10Hibás válasz3ms3108 KiB
subtask30/18
11Hibás válasz3ms2496 KiB
12Elfogadva3ms2448 KiB
13Elfogadva2ms2460 KiB
14Elfogadva3ms2464 KiB
15Elfogadva3ms2796 KiB
16Hibás válasz3ms2836 KiB
17Hibás válasz3ms2956 KiB
18Hibás válasz3ms3108 KiB
19Elfogadva4ms3508 KiB
20Elfogadva35ms4568 KiB
21Elfogadva39ms4428 KiB
22Elfogadva28ms4780 KiB
23Elfogadva27ms4856 KiB
24Hibás válasz26ms4144 KiB
25Hibás válasz25ms4376 KiB
26Hibás válasz25ms4572 KiB
27Hibás válasz24ms4584 KiB
subtask40/25
28Hibás válasz3ms2496 KiB
29Elfogadva3ms2448 KiB
30Elfogadva2ms2460 KiB
31Elfogadva3ms2464 KiB
32Elfogadva3ms2796 KiB
33Hibás válasz3ms2836 KiB
34Hibás válasz3ms2956 KiB
35Hibás válasz3ms3108 KiB
36Időlimit túllépés1.552s39044 KiB
37Időlimit túllépés1.56s39336 KiB
38Időlimit túllépés1.574s39392 KiB
39Időlimit túllépés1.58s39484 KiB
40Időlimit túllépés1.569s39436 KiB
41Időlimit túllépés1.567s39480 KiB
42Időlimit túllépés1.585s39664 KiB
43Időlimit túllépés1.549s39692 KiB
44Időlimit túllépés1.56s39688 KiB
45Időlimit túllépés1.575s39824 KiB
subtask50/24
46Időlimit túllépés1.58s39712 KiB
47Időlimit túllépés1.564s39612 KiB
48Időlimit túllépés1.516s39616 KiB
49Időlimit túllépés1.559s39652 KiB
50Időlimit túllépés1.552s39576 KiB
51Időlimit túllépés1.542s39944 KiB
52Időlimit túllépés1.564s39820 KiB
53Időlimit túllépés1.574s39868 KiB
54Időlimit túllépés1.564s39804 KiB
55Időlimit túllépés1.554s39792 KiB
subtask60/21
56Hibás válasz3ms2496 KiB
57Elfogadva3ms2448 KiB
58Elfogadva2ms2460 KiB
59Elfogadva3ms2464 KiB
60Elfogadva3ms2796 KiB
61Hibás válasz3ms2836 KiB
62Hibás válasz3ms2956 KiB
63Hibás válasz3ms3108 KiB
64Elfogadva4ms3508 KiB
65Elfogadva35ms4568 KiB
66Elfogadva39ms4428 KiB
67Elfogadva28ms4780 KiB
68Elfogadva27ms4856 KiB
69Hibás válasz26ms4144 KiB
70Hibás válasz25ms4376 KiB
71Hibás válasz25ms4572 KiB
72Hibás válasz24ms4584 KiB
73Időlimit túllépés1.552s39044 KiB
74Időlimit túllépés1.56s39336 KiB
75Időlimit túllépés1.574s39392 KiB
76Időlimit túllépés1.58s39484 KiB
77Időlimit túllépés1.569s39436 KiB
78Időlimit túllépés1.567s39480 KiB
79Időlimit túllépés1.585s39664 KiB
80Időlimit túllépés1.549s39692 KiB
81Időlimit túllépés1.56s39688 KiB
82Időlimit túllépés1.575s39824 KiB
83Időlimit túllépés1.58s39712 KiB
84Időlimit túllépés1.564s39612 KiB
85Időlimit túllépés1.516s39616 KiB
86Időlimit túllépés1.559s39652 KiB
87Időlimit túllépés1.552s39576 KiB
88Időlimit túllépés1.542s39944 KiB
89Időlimit túllépés1.564s39820 KiB
90Időlimit túllépés1.574s39868 KiB
91Időlimit túllépés1.564s39804 KiB
92Időlimit túllépés1.554s39792 KiB
93Időlimit túllépés1.601s39824 KiB
94Időlimit túllépés1.575s39760 KiB
95Időlimit túllépés1.544s39888 KiB
96Időlimit túllépés1.567s39944 KiB
97Időlimit túllépés1.575s40036 KiB
98Időlimit túllépés1.562s8516 KiB
99Időlimit túllépés1.564s39976 KiB
100Időlimit túllépés1.562s39992 KiB
101Időlimit túllépés1.559s39940 KiB
102Időlimit túllépés1.574s39924 KiB
103Időlimit túllépés1.585s39820 KiB
104Időlimit túllépés1.57s40016 KiB
105Időlimit túllépés1.555s40008 KiB
106Időlimit túllépés1.56s39972 KiB
107Időlimit túllépés1.565s40040 KiB
108Időlimit túllépés1.569s39968 KiB
109Időlimit túllépés1.565s40132 KiB
110Időlimit túllépés1.544s39920 KiB
111Időlimit túllépés1.575s40064 KiB
112Időlimit túllépés1.547s39856 KiB
113Időlimit túllépés1.575s39932 KiB
114Időlimit túllépés1.567s39936 KiB
115Időlimit túllépés1.559s39944 KiB
116Időlimit túllépés1.572s39868 KiB
117Időlimit túllépés1.57s39924 KiB
118Időlimit túllépés1.555s39964 KiB