fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int maxn = 2e3+5;
  5. const int oo = 1e9 + 7;
  6.  
  7. int n, m, k, s, t;
  8. vector<int> adj[maxn];
  9. int d[maxn][maxn][2];
  10.  
  11. struct que
  12. {
  13.     int u, v, t;
  14. };
  15.  
  16. void solve()
  17. {
  18.     cin >> n >> m >> k >> s >> t;
  19.  
  20.     for(int i = 1; i <= m; i++)
  21.     {
  22.         int u, v;
  23.         cin >> u >> v;
  24.         adj[u].push_back(v);
  25.     }
  26.  
  27.     if(s == t)
  28.     {
  29.         cout << 0 << "\n";
  30.         return;
  31.     }
  32.  
  33.     for(int i = 1; i <= n; i++)
  34.     {
  35.         for(int j = 1; j <= n; j++)
  36.         {
  37.             d[i][j][0] = d[i][j][1] = oo;
  38.         }
  39.     }
  40.  
  41.     queue<que> q;
  42.     d[s][t][0] = 0;
  43.     q.push({s, t, 0});
  44.  
  45.     while(!q.empty())
  46.     {
  47.         que cur = q.front();
  48.         q.pop();
  49.  
  50.         int u = cur.u;
  51.         int v = cur.v;
  52.         int t = cur.t;
  53.  
  54.         if(t == 0)
  55.         {
  56.             for(int x : adj[u])
  57.             {
  58.                 if(d[x][v][1] == oo)
  59.                 {
  60.                     d[x][v][1] = d[u][v][0];
  61.                     q.push({x, v, 1});
  62.                 }
  63.             }
  64.         }
  65.         else
  66.         {
  67.             for(int y : adj[v])
  68.             {
  69.                 if(d[u][y][0] == oo)
  70.                 {
  71.                     d[u][y][0] = d[u][v][1] + 1;
  72.  
  73.                     if(u == y)
  74.                     {
  75.                         cout << d[u][y][0] << "\n";
  76.                         return;
  77.                     }
  78.  
  79.                     q.push({u, y, 0});
  80.                 }
  81.             }
  82.         }
  83.     }
  84.  
  85.     cout << -1 << "\n";
  86. }
  87.  
  88. int32_t main()
  89. {
  90.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  91.     if(fopen("main.inp", "r"))
  92.     {
  93.         freopen("main.inp", "r", stdin);
  94. //        freopen("main.out", "w", stdout);
  95.     }
  96.     int test = 1;
  97. //    cin >> test;
  98.     while(test--) solve();
  99. }
  100.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
5 5 2
1 3
1 2
2 3
3 4
4 5
5 2
stdout
copy 
-1
https://ideone.com/YtSAiU
language:
C++14 (clang 8.0)
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!