162902025-04-21 08:40:36horkaAutó-tortúracpp17Runtime error 12/1001.603s262144 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;
    priority_queue<array<int, 4>> q;
    q.push({0,p[1],1,k});
    while(!q.empty())
    {
        auto [lep,cs,ind,marad]=q.top();
        q.pop();
        lep=abs(lep);
        if(lep!=dp[cs][ind][marad]) continue;
        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({-lep-1,ujcs,ujind,ujmarad});
            }
        }
    }
    cout<<(ans==inf?-1:ans)<<"\n";
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Runtime error196ms262144 KiB
subtask212/12
3Accepted1ms496 KiB
4Accepted1ms316 KiB
5Accepted1ms316 KiB
6Accepted1ms508 KiB
7Accepted1ms380 KiB
8Accepted1ms316 KiB
9Accepted1ms316 KiB
10Accepted1ms420 KiB
subtask30/18
11Accepted1ms496 KiB
12Accepted1ms316 KiB
13Accepted1ms316 KiB
14Accepted1ms508 KiB
15Accepted1ms380 KiB
16Accepted1ms316 KiB
17Accepted1ms316 KiB
18Accepted1ms420 KiB
19Accepted29ms2868 KiB
20Time limit exceeded1.603s65524 KiB
21Runtime error1.23s65504 KiB
22Time limit exceeded1.603s65108 KiB
23Time limit exceeded1.585s65332 KiB
24Runtime error4ms564 KiB
25Runtime error85ms5900 KiB
26Runtime error45ms3892 KiB
27Runtime error1ms316 KiB
subtask40/25
28Accepted1ms496 KiB
29Accepted1ms316 KiB
30Accepted1ms316 KiB
31Accepted1ms508 KiB
32Accepted1ms380 KiB
33Accepted1ms316 KiB
34Accepted1ms316 KiB
35Accepted1ms420 KiB
36Runtime error3ms564 KiB
37Runtime error115ms126588 KiB
38Runtime error3ms564 KiB
39Runtime error3ms536 KiB
40Runtime error94ms126608 KiB
41Time limit exceeded1.588s127060 KiB
42Runtime error3ms564 KiB
43Runtime error43ms40756 KiB
44Runtime error18ms16864 KiB
45Runtime error2ms568 KiB
subtask50/24
46Runtime error204ms262144 KiB
47Runtime error208ms262144 KiB
48Runtime error264ms262144 KiB
49Runtime error259ms262144 KiB
50Runtime error206ms262144 KiB
51Runtime error208ms262144 KiB
52Runtime error263ms262144 KiB
53Runtime error244ms262144 KiB
54Runtime error200ms262144 KiB
55Runtime error200ms262144 KiB
subtask60/21
56Accepted1ms496 KiB
57Accepted1ms316 KiB
58Accepted1ms316 KiB
59Accepted1ms508 KiB
60Accepted1ms380 KiB
61Accepted1ms316 KiB
62Accepted1ms316 KiB
63Accepted1ms420 KiB
64Accepted29ms2868 KiB
65Time limit exceeded1.603s65524 KiB
66Runtime error1.23s65504 KiB
67Time limit exceeded1.603s65108 KiB
68Time limit exceeded1.585s65332 KiB
69Runtime error4ms564 KiB
70Runtime error85ms5900 KiB
71Runtime error45ms3892 KiB
72Runtime error1ms316 KiB
73Runtime error3ms564 KiB
74Runtime error115ms126588 KiB
75Runtime error3ms564 KiB
76Runtime error3ms536 KiB
77Runtime error94ms126608 KiB
78Time limit exceeded1.588s127060 KiB
79Runtime error3ms564 KiB
80Runtime error43ms40756 KiB
81Runtime error18ms16864 KiB
82Runtime error2ms568 KiB
83Runtime error204ms262144 KiB
84Runtime error208ms262144 KiB
85Runtime error264ms262144 KiB
86Runtime error259ms262144 KiB
87Runtime error206ms262144 KiB
88Runtime error208ms262144 KiB
89Runtime error263ms262144 KiB
90Runtime error244ms262144 KiB
91Runtime error200ms262144 KiB
92Runtime error200ms262144 KiB
93Runtime error3ms568 KiB
94Runtime error247ms262144 KiB
95Runtime error202ms262144 KiB
96Runtime error162ms130356 KiB
97Runtime error2ms564 KiB
98Runtime error201ms262144 KiB
99Runtime error245ms262144 KiB
100Runtime error268ms262144 KiB
101Runtime error270ms262144 KiB
102Runtime error206ms262144 KiB
103Runtime error214ms262144 KiB
104Runtime error268ms262144 KiB
105Runtime error217ms262144 KiB
106Runtime error272ms262144 KiB
107Runtime error2ms748 KiB
108Runtime error216ms262144 KiB
109Runtime error272ms262144 KiB
110Runtime error216ms262144 KiB
111Runtime error273ms262144 KiB
112Runtime error214ms262144 KiB
113Runtime error222ms262144 KiB
114Runtime error264ms262144 KiB
115Runtime error254ms262144 KiB
116Runtime error187ms177456 KiB
117Runtime error2ms564 KiB
118Runtime error3ms564 KiB