108082024-04-15 10:30:25AblablablaAutó-tortúracpp17Időlimit túllépés 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";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1812 KiB
2Időlimit túllépés1.57s20936 KiB
subtask20/12
3Futási hiba3ms2376 KiB
4Elfogadva3ms2408 KiB
5Futási hiba3ms2748 KiB
6Futási hiba3ms3028 KiB
7Futási hiba3ms2976 KiB
8Futási hiba3ms3144 KiB
9Futási hiba3ms3232 KiB
10Futási hiba3ms3144 KiB
subtask30/18
11Futási hiba3ms2376 KiB
12Elfogadva3ms2408 KiB
13Futási hiba3ms2748 KiB
14Futási hiba3ms3028 KiB
15Futási hiba3ms2976 KiB
16Futási hiba3ms3144 KiB
17Futási hiba3ms3232 KiB
18Futási hiba3ms3144 KiB
19Futási hiba4ms3348 KiB
20Futási hiba23ms4256 KiB
21Elfogadva28ms4300 KiB
22Futási hiba23ms4256 KiB
23Futási hiba23ms4256 KiB
24Futási hiba23ms4000 KiB
25Futási hiba23ms4100 KiB
26Futási hiba23ms4212 KiB
27Futási hiba23ms4092 KiB
subtask40/25
28Futási hiba3ms2376 KiB
29Elfogadva3ms2408 KiB
30Futási hiba3ms2748 KiB
31Futási hiba3ms3028 KiB
32Futási hiba3ms2976 KiB
33Futási hiba3ms3144 KiB
34Futási hiba3ms3232 KiB
35Futási hiba3ms3144 KiB
36Időlimit túllépés1.562s38204 KiB
37Időlimit túllépés1.541s38496 KiB
38Időlimit túllépés1.567s38476 KiB
39Időlimit túllépés1.555s38652 KiB
40Időlimit túllépés1.564s38564 KiB
41Időlimit túllépés1.555s38620 KiB
42Időlimit túllépés1.552s38648 KiB
43Időlimit túllépés1.567s38720 KiB
44Időlimit túllépés1.57s39056 KiB
45Időlimit túllépés1.552s38896 KiB
subtask50/24
46Időlimit túllépés1.555s39032 KiB
47Időlimit túllépés1.572s38868 KiB
48Időlimit túllépés1.536s38880 KiB
49Időlimit túllépés1.58s38872 KiB
50Időlimit túllépés1.557s39100 KiB
51Időlimit túllépés1.574s39332 KiB
52Időlimit túllépés1.56s39372 KiB
53Időlimit túllépés1.601s39264 KiB
54Időlimit túllépés1.582s39240 KiB
55Időlimit túllépés1.552s39304 KiB
subtask60/21
56Futási hiba3ms2376 KiB
57Elfogadva3ms2408 KiB
58Futási hiba3ms2748 KiB
59Futási hiba3ms3028 KiB
60Futási hiba3ms2976 KiB
61Futási hiba3ms3144 KiB
62Futási hiba3ms3232 KiB
63Futási hiba3ms3144 KiB
64Futási hiba4ms3348 KiB
65Futási hiba23ms4256 KiB
66Elfogadva28ms4300 KiB
67Futási hiba23ms4256 KiB
68Futási hiba23ms4256 KiB
69Futási hiba23ms4000 KiB
70Futási hiba23ms4100 KiB
71Futási hiba23ms4212 KiB
72Futási hiba23ms4092 KiB
73Időlimit túllépés1.562s38204 KiB
74Időlimit túllépés1.541s38496 KiB
75Időlimit túllépés1.567s38476 KiB
76Időlimit túllépés1.555s38652 KiB
77Időlimit túllépés1.564s38564 KiB
78Időlimit túllépés1.555s38620 KiB
79Időlimit túllépés1.552s38648 KiB
80Időlimit túllépés1.567s38720 KiB
81Időlimit túllépés1.57s39056 KiB
82Időlimit túllépés1.552s38896 KiB
83Időlimit túllépés1.555s39032 KiB
84Időlimit túllépés1.572s38868 KiB
85Időlimit túllépés1.536s38880 KiB
86Időlimit túllépés1.58s38872 KiB
87Időlimit túllépés1.557s39100 KiB
88Időlimit túllépés1.574s39332 KiB
89Időlimit túllépés1.56s39372 KiB
90Időlimit túllépés1.601s39264 KiB
91Időlimit túllépés1.582s39240 KiB
92Időlimit túllépés1.552s39304 KiB
93Időlimit túllépés1.572s39312 KiB
94Időlimit túllépés1.546s39268 KiB
95Időlimit túllépés1.526s39332 KiB
96Időlimit túllépés1.562s39520 KiB
97Időlimit túllépés1.546s39564 KiB
98Futási hiba1.248s16872 KiB
99Időlimit túllépés1.577s39504 KiB
100Időlimit túllépés1.565s39456 KiB
101Időlimit túllépés1.557s39488 KiB
102Időlimit túllépés1.549s39492 KiB
103Időlimit túllépés1.57s39764 KiB
104Időlimit túllépés1.57s39800 KiB
105Időlimit túllépés1.58s39804 KiB
106Időlimit túllépés1.58s39952 KiB
107Időlimit túllépés1.554s39900 KiB
108Időlimit túllépés1.56s39764 KiB
109Időlimit túllépés1.554s39656 KiB
110Időlimit túllépés1.565s39756 KiB
111Időlimit túllépés1.572s39828 KiB
112Időlimit túllépés1.555s39804 KiB
113Időlimit túllépés1.585s39760 KiB
114Időlimit túllépés1.57s39952 KiB
115Időlimit túllépés1.562s40020 KiB
116Időlimit túllépés1.572s39956 KiB
117Időlimit túllépés1.555s39960 KiB
118Időlimit túllépés1.565s39972 KiB