제출 #413604

#제출 시각아이디문제언어결과실행 시간메모리
413604iANikzad007 (CEOI14_007)C++14
0 / 100
309 ms25216 KiB
#include<bits/stdc++.h> using namespace std; #define pb push_back #define F first #define S second #define debug(x) cerr<<#x<<" :"<<x<<"\n" #define all(x) x.begin(),x.end() #define pii pair<int,int> #define FAST ios_base::sync_with_stdio(false), cin.tie(), cout.tie(); //#define int long long typedef long long ll; typedef long double ld; const int maxn = 2e5 + 7; const int mod = 1e9 + 7; const int INF = 1e9 + 7; const int mlog = 20; const int SQ = 400; vector<int> adj[maxn]; int dis[4][maxn]; void bfs(int v,int dis[maxn]) { for(int i = 0; i < maxn; i++) dis[i] = +INF; dis[v] = 0; queue<int> q; q.push(v); while(!q.empty()) { v = q.front(), q.pop(); for(int u : adj[v]) if(dis[v] + 1 < dis[u]) dis[u] = dis[v] + 1, q.push(u); } } int32_t main() { FAST; int n, m; cin >> n >> m; int s, d, a, b; cin >> s >> d >> a >> b; for(int i = 0;i < m; i++) { int u, v; cin >> u >> v; adj[u].pb(v), adj[v].pb(u); } bfs(d, dis[0]), bfs(s, dis[1]), bfs(a, dis[2]), bfs(b, dis[3]); int dif1 = dis[0][a] - dis[1][a]; int dif2 = dis[0][b] - dis[1][b]; if(min(dif1, dif2) < 0) return cout << -1 << "\n", 0; if(dif1 != dif2) return cout << min(dif1, dif2) << "\n", 0; int mxS, mxD; mxS = mxD = 0; for(int i = 1; i <= n; i++) if(dis[0][i] + dis[2][i] == dis[0][a] && dis[0][i] + dis[3][i] == dis[0][b]) mxD = max(mxD, dis[0][i]); for(int i = 1; i <= n; i++) if(dis[1][i] + dis[2][i] == dis[1][a] && dis[1][i] + dis[3][i] == dis[1][b]) mxS = max(mxS, dis[1][i]); if(mxS > mxD) cout << dif1 - 1 << "\n"; else cout << dif1 << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...