fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MAXN = 1e5 + 7;
  4. int  n, m, s, t;
  5. long long dist[3][MAXN];
  6. vector <int>a[MAXN];
  7. queue <pair<int, int>> q;
  8.  
  9. int main(){
  10.     ios_base::sync_with_stdio(0);
  11.     cout.tie(0);
  12.     cin.tie(0);
  13.     cin >> n >> m >> s >> t;
  14.     for(int i = 1; i <= m; i++){
  15.         int x, y;
  16.         cin >> x >> y;
  17.         a[x].push_back(y);
  18.         a[y].push_back(x);
  19.     }
  20.     for(int i = 1; i <= n; i++) dist[0][i] = dist[1][i] = INT_MAX;
  21.     q.push({0, s});
  22.     dist[0][s] = 0;
  23.     while(!q.empty()){
  24.         int u = q.front().second;
  25.         int d_u = q.front().first;
  26.         q.pop();
  27.         for(auto v : a[u]){
  28.             if(d_u % 2 == 0){
  29.                 if(dist[1][v] > dist[0][u] + 1){
  30.                     dist[1][v] = dist[0][u] + 1;
  31.                     q.push({dist[1][v], v});
  32.                 }
  33.             }
  34.             else if(d_u % 2 != 0){
  35.                 if(dist[0][v] > dist[1][u] + 1){
  36.                     dist[0][v] = dist[1][u] + 1;
  37.                     q.push({dist[0][v], v});
  38.                 }
  39.             }
  40.         }
  41.     }
  42.     cout << (dist[0][t] == INT_MAX ? -1 : dist[0][t] / 2);
  43. }
Success #stdin #stdout 0.01s 7024KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/KrIU5R
language:
C++14 (gcc 8.3)
created:
3 days 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!