162922025-04-21 08:51:11horkaAutó-tortúracpp17Wrong answer 0/100446ms36088 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 inf=1e7;
    vector<vector<int>> dist(n+1, vector<int> (n+1, inf));
    for(int i=1; i<=n; i++)
    {
        dist[i][i]=0;
        queue<int> q;
        q.push(i);
        while(!q.empty())
        {
            int cs=q.front();
            q.pop();
            for(int &j:adj[cs])
                if(dist[i][cs]+1<dist[i][j])
            {
                dist[i][j]=dist[i][cs]+1;
                q.push(j);
            }
        }
    }
    int l; cin>>l;
    vector<int> p(l+1);
    for(int i=1; i<=l; i++)
        cin>>p[i];
    int b; cin>>b;
    int x; cin>>x;
    int ans=0;
    int ind=1,marad=k;
    while(ind<l)
    {
        int cs=p[ind],kov=p[ind+1];
        if(dist[cs][kov]+(ind+1==l?0:dist[kov][x])<=marad)
        {
            ans+=dist[cs][kov];
            marad-=dist[cs][kov];
            ind++;
        }
        else
        {
            ans+=dist[cs][x];
            if(marad<dist[cs][x])
            {
                cout<<"-1\n";
                return 0;
            }
            marad=k;
            ind++;
            if(dist[x][kov]>k)
            {
                cout<<"-1\n";
                return 0;
            }
            marad-=dist[x][kov];
            ans+=dist[x][kov];
        }
    }
    cout<<ans<<"\n";
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Wrong answer218ms20024 KiB
subtask20/12
3Accepted1ms316 KiB
4Wrong answer1ms316 KiB
5Wrong answer1ms316 KiB
6Wrong answer1ms316 KiB
7Wrong answer1ms316 KiB
8Wrong answer1ms316 KiB
9Wrong answer1ms316 KiB
10Accepted1ms316 KiB
subtask30/18
11Accepted1ms316 KiB
12Wrong answer1ms316 KiB
13Wrong answer1ms316 KiB
14Wrong answer1ms316 KiB
15Wrong answer1ms316 KiB
16Wrong answer1ms316 KiB
17Wrong answer1ms316 KiB
18Accepted1ms316 KiB
19Wrong answer1ms316 KiB
20Wrong answer3ms568 KiB
21Wrong answer2ms564 KiB
22Wrong answer3ms564 KiB
23Wrong answer3ms564 KiB
24Wrong answer3ms564 KiB
25Wrong answer3ms564 KiB
26Wrong answer3ms612 KiB
27Wrong answer2ms564 KiB
subtask40/25
28Accepted1ms316 KiB
29Wrong answer1ms316 KiB
30Wrong answer1ms316 KiB
31Wrong answer1ms316 KiB
32Wrong answer1ms316 KiB
33Wrong answer1ms316 KiB
34Wrong answer1ms316 KiB
35Accepted1ms316 KiB
36Accepted435ms35796 KiB
37Accepted389ms35792 KiB
38Accepted444ms35984 KiB
39Wrong answer435ms35984 KiB
40Wrong answer409ms35892 KiB
41Wrong answer370ms35892 KiB
42Wrong answer416ms35892 KiB
43Wrong answer287ms35944 KiB
44Wrong answer287ms35892 KiB
45Wrong answer109ms35892 KiB
subtask50/24
46Wrong answer446ms35892 KiB
47Wrong answer381ms35892 KiB
48Wrong answer435ms35896 KiB
49Wrong answer418ms35892 KiB
50Wrong answer250ms35808 KiB
51Wrong answer444ms35892 KiB
52Wrong answer381ms35892 KiB
53Wrong answer444ms35892 KiB
54Accepted409ms35892 KiB
55Wrong answer250ms35892 KiB
subtask60/21
56Accepted1ms316 KiB
57Wrong answer1ms316 KiB
58Wrong answer1ms316 KiB
59Wrong answer1ms316 KiB
60Wrong answer1ms316 KiB
61Wrong answer1ms316 KiB
62Wrong answer1ms316 KiB
63Accepted1ms316 KiB
64Wrong answer1ms316 KiB
65Wrong answer3ms568 KiB
66Wrong answer2ms564 KiB
67Wrong answer3ms564 KiB
68Wrong answer3ms564 KiB
69Wrong answer3ms564 KiB
70Wrong answer3ms564 KiB
71Wrong answer3ms612 KiB
72Wrong answer2ms564 KiB
73Accepted435ms35796 KiB
74Accepted389ms35792 KiB
75Accepted444ms35984 KiB
76Wrong answer435ms35984 KiB
77Wrong answer409ms35892 KiB
78Wrong answer370ms35892 KiB
79Wrong answer416ms35892 KiB
80Wrong answer287ms35944 KiB
81Wrong answer287ms35892 KiB
82Wrong answer109ms35892 KiB
83Wrong answer446ms35892 KiB
84Wrong answer381ms35892 KiB
85Wrong answer435ms35896 KiB
86Wrong answer418ms35892 KiB
87Wrong answer250ms35808 KiB
88Wrong answer444ms35892 KiB
89Wrong answer381ms35892 KiB
90Wrong answer444ms35892 KiB
91Accepted409ms35892 KiB
92Wrong answer250ms35892 KiB
93Wrong answer307ms36088 KiB
94Wrong answer305ms35892 KiB
95Wrong answer416ms35892 KiB
96Wrong answer442ms35896 KiB
97Wrong answer112ms35892 KiB
98Wrong answer21ms4244 KiB
99Wrong answer421ms35892 KiB
100Wrong answer439ms36036 KiB
101Wrong answer444ms35892 KiB
102Wrong answer430ms35836 KiB
103Wrong answer310ms35892 KiB
104Wrong answer175ms35900 KiB
105Wrong answer317ms35956 KiB
106Wrong answer296ms36000 KiB
107Wrong answer287ms35904 KiB
108Wrong answer409ms35904 KiB
109Wrong answer111ms35836 KiB
110Wrong answer310ms35904 KiB
111Wrong answer400ms35904 KiB
112Wrong answer310ms35904 KiB
113Wrong answer337ms35904 KiB
114Wrong answer419ms35904 KiB
115Wrong answer430ms35904 KiB
116Wrong answer432ms35904 KiB
117Wrong answer305ms35904 KiB
118Wrong answer111ms35904 KiB