제출 #449636

#제출 시각아이디문제언어결과실행 시간메모리
449636vanic007 (CEOI14_007)C++14
0 / 100
285 ms33044 KiB
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <vector> #include <cstring> #include <queue> #include <cassert> using namespace std; const int maxn=2e5+5; vector < int > ms[maxn]; int dist[2][maxn]; void bfs(int x, int ind){ queue < int > q; q.push(x); dist[ind][x]=0; while(!q.empty()){ x=q.front(); q.pop(); for(int i=0; i<(int)ms[x].size(); i++){ if(dist[ind][ms[x][i]]==-1){ dist[ind][ms[x][i]]=dist[ind][x]+1; q.push(ms[x][i]); } } } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); memset(dist, -1, sizeof(dist)); int n, m; cin >> n >> m; int a, b, c, d; cin >> a >> b >> c >> d; a--; b--; c--; d--; int x, y; for(int i=0; i<m; i++){ cin >> x >> y; x--; y--; ms[x].push_back(y); ms[y].push_back(x); } bfs(a, 0); bfs(b, 1); if(dist[0][c]>dist[1][c] || dist[0][d]>dist[1][d]){ cout << -1 << '\n'; } else{ assert(0); cout << min(dist[1][c]-dist[0][c], dist[1][d]-dist[0][d]) << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...