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