Submission #613903

#TimeUsernameProblemLanguageResultExecution timeMemory
613903andrei_boaca007 (CEOI14_007)C++14
30 / 100
218 ms17592 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; int n,m,s,d,a,b; vector<int> muchii[200005]; int dist[5][200005]; void bfs(int start,int index) { for(int i=1;i<=n;i++) dist[index][i]=1e9; dist[index][start]=0; queue<int> coada; coada.push(start); while(!coada.empty()) { int nod=coada.front(); coada.pop(); for(int i:muchii[nod]) if(dist[index][i]>dist[index][nod]+1) { dist[index][i]=dist[index][nod]+1; coada.push(i); } } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin>>n>>m>>s>>d>>a>>b; for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; muchii[x].push_back(y); muchii[y].push_back(x); } bfs(a,1); bfs(b,2); bfs(d,3); bfs(s,4); int minim=1e9; for(int i=1;i<=n;i++) { bool good; if(dist[4][i]<=1) good=1; else { good=0; if(dist[1][i]>=dist[1][s]) { if(dist[2][i]+1>=dist[2][s]) good=1; } if(dist[2][i]>=dist[2][s]) { if(dist[1][i]+1>=dist[1][s]) good=1; } } if(!good) minim=min(minim,dist[3][i]-2); } int ans=max(-1,minim); if(s==a||s==b) ans++; cout<<ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...