162912025-04-21 08:42:39horkaAutó-tortúracpp17Runtime error 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";
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Runtime error194ms262144 KiB
subtask212/12
3Accepted1ms508 KiB
4Accepted1ms508 KiB
5Accepted1ms316 KiB
6Accepted1ms316 KiB
7Accepted1ms316 KiB
8Accepted1ms316 KiB
9Accepted1ms316 KiB
10Accepted1ms396 KiB
subtask30/18
11Accepted1ms508 KiB
12Accepted1ms508 KiB
13Accepted1ms316 KiB
14Accepted1ms316 KiB
15Accepted1ms316 KiB
16Accepted1ms316 KiB
17Accepted1ms316 KiB
18Accepted1ms396 KiB
19Accepted9ms2928 KiB
20Runtime error982ms65132 KiB
21Runtime error412ms65300 KiB
22Runtime error648ms65204 KiB
23Runtime error947ms65072 KiB
24Runtime error2ms564 KiB
25Runtime error43ms5876 KiB
26Runtime error21ms3916 KiB
27Runtime error1ms316 KiB
subtask40/25
28Accepted1ms508 KiB
29Accepted1ms508 KiB
30Accepted1ms316 KiB
31Accepted1ms316 KiB
32Accepted1ms316 KiB
33Accepted1ms316 KiB
34Accepted1ms316 KiB
35Accepted1ms396 KiB
36Runtime error3ms564 KiB
37Runtime error96ms126640 KiB
38Runtime error3ms564 KiB
39Runtime error3ms564 KiB
40Runtime error93ms126516 KiB
41Time limit exceeded1.608s126996 KiB
42Runtime error3ms564 KiB
43Runtime error32ms40500 KiB
44Runtime error17ms16948 KiB
45Runtime error2ms564 KiB
subtask50/24
46Runtime error207ms262144 KiB
47Runtime error207ms262144 KiB
48Runtime error263ms262144 KiB
49Runtime error259ms262144 KiB
50Runtime error209ms262144 KiB
51Runtime error202ms262144 KiB
52Runtime error201ms262144 KiB
53Runtime error247ms262144 KiB
54Runtime error244ms262144 KiB
55Runtime error202ms262144 KiB
subtask60/21
56Accepted1ms508 KiB
57Accepted1ms508 KiB
58Accepted1ms316 KiB
59Accepted1ms316 KiB
60Accepted1ms316 KiB
61Accepted1ms316 KiB
62Accepted1ms316 KiB
63Accepted1ms396 KiB
64Accepted9ms2928 KiB
65Runtime error982ms65132 KiB
66Runtime error412ms65300 KiB
67Runtime error648ms65204 KiB
68Runtime error947ms65072 KiB
69Runtime error2ms564 KiB
70Runtime error43ms5876 KiB
71Runtime error21ms3916 KiB
72Runtime error1ms316 KiB
73Runtime error3ms564 KiB
74Runtime error96ms126640 KiB
75Runtime error3ms564 KiB
76Runtime error3ms564 KiB
77Runtime error93ms126516 KiB
78Time limit exceeded1.608s126996 KiB
79Runtime error3ms564 KiB
80Runtime error32ms40500 KiB
81Runtime error17ms16948 KiB
82Runtime error2ms564 KiB
83Runtime error207ms262144 KiB
84Runtime error207ms262144 KiB
85Runtime error263ms262144 KiB
86Runtime error259ms262144 KiB
87Runtime error209ms262144 KiB
88Runtime error202ms262144 KiB
89Runtime error201ms262144 KiB
90Runtime error247ms262144 KiB
91Runtime error244ms262144 KiB
92Runtime error202ms262144 KiB
93Runtime error3ms564 KiB
94Runtime error252ms262144 KiB
95Runtime error203ms262144 KiB
96Runtime error163ms130284 KiB
97Runtime error2ms564 KiB
98Runtime error199ms262144 KiB
99Runtime error240ms262144 KiB
100Runtime error263ms262144 KiB
101Runtime error280ms262144 KiB
102Runtime error211ms262144 KiB
103Runtime error223ms262144 KiB
104Runtime error277ms262144 KiB
105Runtime error222ms262144 KiB
106Runtime error273ms262144 KiB
107Runtime error2ms564 KiB
108Runtime error222ms262144 KiB
109Runtime error273ms262144 KiB
110Runtime error219ms262144 KiB
111Runtime error273ms262144 KiB
112Runtime error224ms262144 KiB
113Runtime error268ms262144 KiB
114Runtime error225ms262144 KiB
115Runtime error256ms262144 KiB
116Runtime error153ms177456 KiB
117Runtime error2ms564 KiB
118Runtime error2ms564 KiB