fork download 
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3. #define pii pair<int,int>
  4. #define fi first
  5. #define int long long
  6. #define se second
  7. #define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  8. #define TXT "test"
  9. #define freo if(fopen(TXT".inp","r")){freopen(TXT".inp","r",stdin); freopen(TXT".out","w",stdout);}
  10.  
  11. using namespace std;
  12.  
  13. const int MXN = 1e5 + 5;
  14.  
  15. int n, m, s, t;
  16. vector<int> a[MXN];
  17. int dis[MXN], par[MXN];
  18.  
  19. void solve()
  20. {
  21.     cin >> n >> m >> s >> t;
  22.     for (int i = 1; i <= m; i++)
  23.     {
  24.         int u, v;
  25.         cin >> u >> v;
  26.         a[u].push_back(v);
  27.         a[v].push_back(u);
  28.     }
  29.  
  30.     memset(dis, -1, sizeof dis);
  31.     queue<int> q;
  32.     dis[s] = 0;
  33.     q.push(s);
  34.  
  35.     while (!q.empty())
  36.     {
  37.         int u = q.front();
  38.         q.pop();
  39.         for (int v : a[u])
  40.         {
  41.             if (dis[v] == -1)
  42.             {
  43.                 dis[v] = dis[u] + 1;
  44.                 q.push(v);
  45.             }
  46.         }
  47.     }
  48.  
  49.     if (dis[t] == -1)
  50.     {
  51.         cout << -1;
  52.         return;
  53.     }
  54.  
  55.     memset(par, -1, sizeof par);
  56.     vector<int> res;
  57.     int cur = t;
  58.  
  59.     while (cur != s)
  60.     {
  61.         res.push_back(cur);
  62.         int best = -1;
  63.         for (int v : a[cur])
  64.         {
  65.             if (dis[v] == dis[cur] - 1)
  66.             {
  67.                 if (best == -1 || v < best)
  68.                 {
  69.                     best = v;
  70.                 }
  71.             }
  72.         }
  73.         if (best == -1)
  74.         {
  75.             cout << -1;
  76.             return;
  77.         }
  78.         par[cur] = best;
  79.         cur = best;
  80.     }
  81.     res.push_back(s);
  82.     reverse(res.begin(), res.end());
  83.     for (int x : res) cout << x << " ";
  84. }
  85. main()
  86. {
  87.     ios;
  88.     freo;
  89.     solve();
  90. }
Success #stdin #stdout 0.01s 7412KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/x1NF3M
language:
C++ (gcc 8.3)
created:
6 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!