fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long MaxN = 1e5 + 5;
  5. const long long MaxVal = 1e18;
  6.  
  7. long long n,m,a,b;
  8.  
  9. vector<long long> arr[MaxN];
  10.  
  11. bool Check_A[2][MaxN];
  12. bool Check_B[2][MaxN];
  13.  
  14. long long Min_SumA[2][MaxN];
  15. long long Min_SumB[2][MaxN];
  16.  
  17. void bfs(long long x, vector<long long> arr[], bool Check[2][MaxN], long long Min_Sum[2][MaxN])
  18. {
  19.     queue<pair<long long,long long>> qu;
  20.  
  21.     qu.push({x,0});
  22.  
  23.     Check[0][x]=true;
  24.     Min_Sum[0][x]=0;
  25.  
  26.     while(!qu.empty())
  27.     {
  28.         long long u=qu.front().first;
  29.         long long parity=qu.front().second;
  30.         qu.pop();
  31.  
  32.         long long new_dis=Min_Sum[parity][u]+1;
  33.         long long new_parity=1-parity;
  34.  
  35.         for(long long v:arr[u])
  36.         {
  37.             if(!Check[new_parity][v])
  38.             {
  39.                 Check[new_parity][v]=true;
  40.                 Min_Sum[new_parity][v]=new_dis;
  41.  
  42.                 qu.push({v,new_parity});
  43.             }
  44.         }
  45.     }
  46. }
  47.  
  48. void input()
  49. {
  50.     cin>>n>>m;
  51.     cin>>a>>b;
  52.  
  53.     for(long long i=1;i<=m;i++)
  54.     {
  55.         long long u,v;
  56.  
  57.         cin>>u>>v;
  58.  
  59.         arr[u].push_back(v);
  60.         arr[v].push_back(u);
  61.     }
  62. }
  63.  
  64. void solve()
  65. {
  66.     for(long long i=1;i<=n;i++)
  67.     {
  68.         for(long long j=0;j<=1;j++)
  69.         {
  70.             Check_A[j][i]=false;
  71.             Check_B[j][i]=false;
  72.  
  73.             Min_SumA[j][i]=MaxVal;
  74.             Min_SumB[j][i]=MaxVal;
  75.         }
  76.     }
  77.  
  78.     bfs(a,arr,Check_A,Min_SumA);
  79.     bfs(b,arr,Check_B,Min_SumB);
  80.  
  81.     long long ans=MaxVal;
  82.  
  83.     for(long long i=1;i<=n;i++)
  84.     {
  85.         for(long long j=0;j<=1;j++)
  86.         {
  87.             if(Check_A[j][i] && Check_B[j][i])
  88.             {
  89.                 ans=min(ans,max(Min_SumA[j][i],Min_SumB[j][i]));
  90.             }
  91.         }
  92.     }
  93.  
  94.     if(ans==MaxVal)
  95.     {
  96.         cout<<-1;
  97.     }
  98.     else
  99.     {
  100.         cout<<ans;
  101.     }
  102. }
  103.  
  104. int main()
  105. {
  106.     ios_base::sync_with_stdio(0);
  107.     cin.tie(0);
  108.  
  109.     input();
  110.     solve();
  111. }
Success #stdin #stdout 0.01s 8076KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/eWhdL3
language:
C++14 (gcc 8.3)
created:
4 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!