162912025-04-21 08:42:39horkaAutó-tortúracpp17Futási hiba 12/1001.608s262144 KiB
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,m,k; cin>>n>>m>>k;
    vector<vector<int>> adj(n+1);
    while(m--)
    {
        int a,b; cin>>a>>b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    int l; cin>>l;
    vector<int> p(l+1);
    for(int i=1; i<=l; i++)
        cin>>p[i];
    int b; cin>>b;
    vector<bool> benz(b+1);
    while(b--)
    {
        int x; cin>>x;
        benz[x]=1;
    }
    int inf=1e8,ans=1e8;
    vector<vector<vector<int>>> dp(n+1, vector<vector<int>> (l+1, vector<int> (k+1, inf)));
    dp[p[1]][1][k]=0;
    queue<array<int, 3>> q;
    q.push({p[1],1,k});
    while(!q.empty())
    {
        auto [cs,ind,marad]=q.front();
        q.pop();
        int lep=dp[cs][ind][marad];
        if(ind==l)
        {
            ans=min(ans,lep);
            break;
        }
        if(marad==0) continue;
        for(int &i:adj[cs])
        {
            int ujcs=i,ujind=(i==p[ind+1]?ind+1:ind);
            int ujmarad=(benz[i]?k:marad-1);
            if(lep+1<dp[ujcs][ujind][ujmarad])
            {
                dp[ujcs][ujind][ujmarad]=lep+1;
                q.push({ujcs,ujind,ujmarad});
            }
        }
    }
    cout<<(ans==inf?-1:ans)<<"\n";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Futási hiba194ms262144 KiB
subtask212/12
3Elfogadva1ms508 KiB
4Elfogadva1ms508 KiB
5Elfogadva1ms316 KiB
6Elfogadva1ms316 KiB
7Elfogadva1ms316 KiB
8Elfogadva1ms316 KiB
9Elfogadva1ms316 KiB
10Elfogadva1ms396 KiB
subtask30/18
11Elfogadva1ms508 KiB
12Elfogadva1ms508 KiB
13Elfogadva1ms316 KiB
14Elfogadva1ms316 KiB
15Elfogadva1ms316 KiB
16Elfogadva1ms316 KiB
17Elfogadva1ms316 KiB
18Elfogadva1ms396 KiB
19Elfogadva9ms2928 KiB
20Futási hiba982ms65132 KiB
21Futási hiba412ms65300 KiB
22Futási hiba648ms65204 KiB
23Futási hiba947ms65072 KiB
24Futási hiba2ms564 KiB
25Futási hiba43ms5876 KiB
26Futási hiba21ms3916 KiB
27Futási hiba1ms316 KiB
subtask40/25
28Elfogadva1ms508 KiB
29Elfogadva1ms508 KiB
30Elfogadva1ms316 KiB
31Elfogadva1ms316 KiB
32Elfogadva1ms316 KiB
33Elfogadva1ms316 KiB
34Elfogadva1ms316 KiB
35Elfogadva1ms396 KiB
36Futási hiba3ms564 KiB
37Futási hiba96ms126640 KiB
38Futási hiba3ms564 KiB
39Futási hiba3ms564 KiB
40Futási hiba93ms126516 KiB
41Időlimit túllépés1.608s126996 KiB
42Futási hiba3ms564 KiB
43Futási hiba32ms40500 KiB
44Futási hiba17ms16948 KiB
45Futási hiba2ms564 KiB
subtask50/24
46Futási hiba207ms262144 KiB
47Futási hiba207ms262144 KiB
48Futási hiba263ms262144 KiB
49Futási hiba259ms262144 KiB
50Futási hiba209ms262144 KiB
51Futási hiba202ms262144 KiB
52Futási hiba201ms262144 KiB
53Futási hiba247ms262144 KiB
54Futási hiba244ms262144 KiB
55Futási hiba202ms262144 KiB
subtask60/21
56Elfogadva1ms508 KiB
57Elfogadva1ms508 KiB
58Elfogadva1ms316 KiB
59Elfogadva1ms316 KiB
60Elfogadva1ms316 KiB
61Elfogadva1ms316 KiB
62Elfogadva1ms316 KiB
63Elfogadva1ms396 KiB
64Elfogadva9ms2928 KiB
65Futási hiba982ms65132 KiB
66Futási hiba412ms65300 KiB
67Futási hiba648ms65204 KiB
68Futási hiba947ms65072 KiB
69Futási hiba2ms564 KiB
70Futási hiba43ms5876 KiB
71Futási hiba21ms3916 KiB
72Futási hiba1ms316 KiB
73Futási hiba3ms564 KiB
74Futási hiba96ms126640 KiB
75Futási hiba3ms564 KiB
76Futási hiba3ms564 KiB
77Futási hiba93ms126516 KiB
78Időlimit túllépés1.608s126996 KiB
79Futási hiba3ms564 KiB
80Futási hiba32ms40500 KiB
81Futási hiba17ms16948 KiB
82Futási hiba2ms564 KiB
83Futási hiba207ms262144 KiB
84Futási hiba207ms262144 KiB
85Futási hiba263ms262144 KiB
86Futási hiba259ms262144 KiB
87Futási hiba209ms262144 KiB
88Futási hiba202ms262144 KiB
89Futási hiba201ms262144 KiB
90Futási hiba247ms262144 KiB
91Futási hiba244ms262144 KiB
92Futási hiba202ms262144 KiB
93Futási hiba3ms564 KiB
94Futási hiba252ms262144 KiB
95Futási hiba203ms262144 KiB
96Futási hiba163ms130284 KiB
97Futási hiba2ms564 KiB
98Futási hiba199ms262144 KiB
99Futási hiba240ms262144 KiB
100Futási hiba263ms262144 KiB
101Futási hiba280ms262144 KiB
102Futási hiba211ms262144 KiB
103Futási hiba223ms262144 KiB
104Futási hiba277ms262144 KiB
105Futási hiba222ms262144 KiB
106Futási hiba273ms262144 KiB
107Futási hiba2ms564 KiB
108Futási hiba222ms262144 KiB
109Futási hiba273ms262144 KiB
110Futási hiba219ms262144 KiB
111Futási hiba273ms262144 KiB
112Futási hiba224ms262144 KiB
113Futási hiba268ms262144 KiB
114Futási hiba225ms262144 KiB
115Futási hiba256ms262144 KiB
116Futási hiba153ms177456 KiB
117Futási hiba2ms564 KiB
118Futási hiba2ms564 KiB