162902025-04-21 08:40:36horkaAutó-tortúracpp17Futási hiba 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";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Futási hiba196ms262144 KiB
subtask212/12
3Elfogadva1ms496 KiB
4Elfogadva1ms316 KiB
5Elfogadva1ms316 KiB
6Elfogadva1ms508 KiB
7Elfogadva1ms380 KiB
8Elfogadva1ms316 KiB
9Elfogadva1ms316 KiB
10Elfogadva1ms420 KiB
subtask30/18
11Elfogadva1ms496 KiB
12Elfogadva1ms316 KiB
13Elfogadva1ms316 KiB
14Elfogadva1ms508 KiB
15Elfogadva1ms380 KiB
16Elfogadva1ms316 KiB
17Elfogadva1ms316 KiB
18Elfogadva1ms420 KiB
19Elfogadva29ms2868 KiB
20Időlimit túllépés1.603s65524 KiB
21Futási hiba1.23s65504 KiB
22Időlimit túllépés1.603s65108 KiB
23Időlimit túllépés1.585s65332 KiB
24Futási hiba4ms564 KiB
25Futási hiba85ms5900 KiB
26Futási hiba45ms3892 KiB
27Futási hiba1ms316 KiB
subtask40/25
28Elfogadva1ms496 KiB
29Elfogadva1ms316 KiB
30Elfogadva1ms316 KiB
31Elfogadva1ms508 KiB
32Elfogadva1ms380 KiB
33Elfogadva1ms316 KiB
34Elfogadva1ms316 KiB
35Elfogadva1ms420 KiB
36Futási hiba3ms564 KiB
37Futási hiba115ms126588 KiB
38Futási hiba3ms564 KiB
39Futási hiba3ms536 KiB
40Futási hiba94ms126608 KiB
41Időlimit túllépés1.588s127060 KiB
42Futási hiba3ms564 KiB
43Futási hiba43ms40756 KiB
44Futási hiba18ms16864 KiB
45Futási hiba2ms568 KiB
subtask50/24
46Futási hiba204ms262144 KiB
47Futási hiba208ms262144 KiB
48Futási hiba264ms262144 KiB
49Futási hiba259ms262144 KiB
50Futási hiba206ms262144 KiB
51Futási hiba208ms262144 KiB
52Futási hiba263ms262144 KiB
53Futási hiba244ms262144 KiB
54Futási hiba200ms262144 KiB
55Futási hiba200ms262144 KiB
subtask60/21
56Elfogadva1ms496 KiB
57Elfogadva1ms316 KiB
58Elfogadva1ms316 KiB
59Elfogadva1ms508 KiB
60Elfogadva1ms380 KiB
61Elfogadva1ms316 KiB
62Elfogadva1ms316 KiB
63Elfogadva1ms420 KiB
64Elfogadva29ms2868 KiB
65Időlimit túllépés1.603s65524 KiB
66Futási hiba1.23s65504 KiB
67Időlimit túllépés1.603s65108 KiB
68Időlimit túllépés1.585s65332 KiB
69Futási hiba4ms564 KiB
70Futási hiba85ms5900 KiB
71Futási hiba45ms3892 KiB
72Futási hiba1ms316 KiB
73Futási hiba3ms564 KiB
74Futási hiba115ms126588 KiB
75Futási hiba3ms564 KiB
76Futási hiba3ms536 KiB
77Futási hiba94ms126608 KiB
78Időlimit túllépés1.588s127060 KiB
79Futási hiba3ms564 KiB
80Futási hiba43ms40756 KiB
81Futási hiba18ms16864 KiB
82Futási hiba2ms568 KiB
83Futási hiba204ms262144 KiB
84Futási hiba208ms262144 KiB
85Futási hiba264ms262144 KiB
86Futási hiba259ms262144 KiB
87Futási hiba206ms262144 KiB
88Futási hiba208ms262144 KiB
89Futási hiba263ms262144 KiB
90Futási hiba244ms262144 KiB
91Futási hiba200ms262144 KiB
92Futási hiba200ms262144 KiB
93Futási hiba3ms568 KiB
94Futási hiba247ms262144 KiB
95Futási hiba202ms262144 KiB
96Futási hiba162ms130356 KiB
97Futási hiba2ms564 KiB
98Futási hiba201ms262144 KiB
99Futási hiba245ms262144 KiB
100Futási hiba268ms262144 KiB
101Futási hiba270ms262144 KiB
102Futási hiba206ms262144 KiB
103Futási hiba214ms262144 KiB
104Futási hiba268ms262144 KiB
105Futási hiba217ms262144 KiB
106Futási hiba272ms262144 KiB
107Futási hiba2ms748 KiB
108Futási hiba216ms262144 KiB
109Futási hiba272ms262144 KiB
110Futási hiba216ms262144 KiB
111Futási hiba273ms262144 KiB
112Futási hiba214ms262144 KiB
113Futási hiba222ms262144 KiB
114Futási hiba264ms262144 KiB
115Futási hiba254ms262144 KiB
116Futási hiba187ms177456 KiB
117Futási hiba2ms564 KiB
118Futási hiba3ms564 KiB