108072024-04-15 10:27:30AblablablaAutó-tortúracpp17Időlimit túllépés 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";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1812 KiB
2Időlimit túllépés1.555s20924 KiB
subtask20/12
3Futási hiba3ms2728 KiB
4Futási hiba3ms2644 KiB
5Futási hiba3ms2848 KiB
6Futási hiba3ms3052 KiB
7Hibás válasz2ms2956 KiB
8Hibás válasz3ms3064 KiB
9Futási hiba3ms3288 KiB
10Hibás válasz3ms3168 KiB
subtask30/18
11Futási hiba3ms2728 KiB
12Futási hiba3ms2644 KiB
13Futási hiba3ms2848 KiB
14Futási hiba3ms3052 KiB
15Hibás válasz2ms2956 KiB
16Hibás válasz3ms3064 KiB
17Futási hiba3ms3288 KiB
18Hibás válasz3ms3168 KiB
19Futási hiba4ms3576 KiB
20Futási hiba3ms4044 KiB
21Futási hiba3ms4260 KiB
22Futási hiba3ms4520 KiB
23Futási hiba3ms4728 KiB
24Futási hiba30ms4692 KiB
25Futási hiba30ms4792 KiB
26Futási hiba30ms4904 KiB
27Futási hiba29ms4904 KiB
subtask40/25
28Futási hiba3ms2728 KiB
29Futási hiba3ms2644 KiB
30Futási hiba3ms2848 KiB
31Futási hiba3ms3052 KiB
32Hibás válasz2ms2956 KiB
33Hibás válasz3ms3064 KiB
34Futási hiba3ms3288 KiB
35Hibás válasz3ms3168 KiB
36Időlimit túllépés1.57s39024 KiB
37Időlimit túllépés1.526s39140 KiB
38Időlimit túllépés1.585s39288 KiB
39Időlimit túllépés1.537s39396 KiB
40Időlimit túllépés1.58s39356 KiB
41Időlimit túllépés1.57s39440 KiB
42Időlimit túllépés1.565s39636 KiB
43Időlimit túllépés1.575s39592 KiB
44Időlimit túllépés1.564s39656 KiB
45Időlimit túllépés1.57s39788 KiB
subtask50/24
46Időlimit túllépés1.577s39724 KiB
47Időlimit túllépés1.542s39664 KiB
48Időlimit túllépés1.57s39620 KiB
49Időlimit túllépés1.577s39596 KiB
50Időlimit túllépés1.565s39588 KiB
51Időlimit túllépés1.562s39700 KiB
52Időlimit túllépés1.56s39748 KiB
53Időlimit túllépés1.574s39700 KiB
54Időlimit túllépés1.569s39648 KiB
55Időlimit túllépés1.562s39580 KiB
subtask60/21
56Futási hiba3ms2728 KiB
57Futási hiba3ms2644 KiB
58Futási hiba3ms2848 KiB
59Futási hiba3ms3052 KiB
60Hibás válasz2ms2956 KiB
61Hibás válasz3ms3064 KiB
62Futási hiba3ms3288 KiB
63Hibás válasz3ms3168 KiB
64Futási hiba4ms3576 KiB
65Futási hiba3ms4044 KiB
66Futási hiba3ms4260 KiB
67Futási hiba3ms4520 KiB
68Futási hiba3ms4728 KiB
69Futási hiba30ms4692 KiB
70Futási hiba30ms4792 KiB
71Futási hiba30ms4904 KiB
72Futási hiba29ms4904 KiB
73Időlimit túllépés1.57s39024 KiB
74Időlimit túllépés1.526s39140 KiB
75Időlimit túllépés1.585s39288 KiB
76Időlimit túllépés1.537s39396 KiB
77Időlimit túllépés1.58s39356 KiB
78Időlimit túllépés1.57s39440 KiB
79Időlimit túllépés1.565s39636 KiB
80Időlimit túllépés1.575s39592 KiB
81Időlimit túllépés1.564s39656 KiB
82Időlimit túllépés1.57s39788 KiB
83Időlimit túllépés1.577s39724 KiB
84Időlimit túllépés1.542s39664 KiB
85Időlimit túllépés1.57s39620 KiB
86Időlimit túllépés1.577s39596 KiB
87Időlimit túllépés1.565s39588 KiB
88Időlimit túllépés1.562s39700 KiB
89Időlimit túllépés1.56s39748 KiB
90Időlimit túllépés1.574s39700 KiB
91Időlimit túllépés1.569s39648 KiB
92Időlimit túllépés1.562s39580 KiB
93Időlimit túllépés1.577s39756 KiB
94Időlimit túllépés1.585s39868 KiB
95Időlimit túllépés1.57s39892 KiB
96Időlimit túllépés1.57s39880 KiB
97Időlimit túllépés1.577s39804 KiB
98Időlimit túllépés1.559s8380 KiB
99Időlimit túllépés1.57s39688 KiB
100Időlimit túllépés1.562s39620 KiB
101Futási hiba39ms76024 KiB
102Időlimit túllépés1.554s39744 KiB
103Futási hiba35ms76044 KiB
104Futási hiba35ms75948 KiB
105Futási hiba29ms76028 KiB
106Futási hiba35ms76144 KiB
107Futási hiba37ms76028 KiB
108Futási hiba39ms76060 KiB
109Futási hiba35ms75936 KiB
110Futási hiba30ms76024 KiB
111Futási hiba39ms76224 KiB
112Futási hiba37ms76268 KiB
113Futási hiba37ms76388 KiB
114Időlimit túllépés1.57s39976 KiB
115Időlimit túllépés1.562s39892 KiB
116Időlimit túllépés1.565s39880 KiB
117Időlimit túllépés1.557s39960 KiB
118Időlimit túllépés1.572s39964 KiB