fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FIO ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
  3. #define ll long long
  4. #define ull unsigned long long
  5. #define ld long double
  6. #define Yes cout << "YES\n"
  7. #define No  cout << "NO\n"
  8. using namespace std;
  9. #define IO freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
  10. const int MX = 2e5 + 5 , MOD = 1e9 + 7;
  11. #define all(v) v.begin() , v.end()
  12. #define rall(v) v.rbegin() , v.rend()
  13. #define nl '\n'
  14.  
  15. vector<vector<int>>adj(MX);
  16. vector<int>indeg(MX);
  17. vector<bool>vis(MX);
  18. vector<bool>inprogg(MX);
  19. queue<int>q;
  20. vector<int>ans(MX);
  21. vector<int>parent(MX);
  22. void solve()
  23. {
  24.     int n , m;
  25.     cin >> n >> m;
  26.     for(int i = 0; i <m ; i++){
  27.         int u,v;
  28.         cin>> u >> v;
  29.         adj[u].push_back(v);
  30.         adj[v].push_back(u);
  31.     }
  32.     q.push(1);
  33.     vis[1] = true;
  34.     while(!q.empty())
  35.     {
  36.         int node = q.front(); q.pop();
  37.         for(auto& i : adj[node]){
  38.             if(!vis[i]){
  39.                 ans[i] = ans[node] + 1;
  40.                 vis[i] = true;
  41.                 q.push(i);
  42.                 parent[i] = node;
  43.             }
  44.         }
  45.     }
  46.  
  47.     if(!vis[n]){
  48.         cout << "IMPOSSIBLE";
  49.         return;
  50.     }
  51.     cout << ans[n] + 1 << nl;
  52.     vector<int>res;
  53.     int x = n; res.push_back(x);
  54.     while(x > 1){
  55.         res.push_back(parent[x]);
  56.         x = parent[x];
  57.     }
  58.  
  59.     reverse(all(res));
  60.     for(auto& i : res)
  61.         cout << i << ' ';
  62. }
  63.  
  64. int main()
  65. {
  66.     FIO
  67. #ifndef ONLINE_JUDGE
  68.     IO
  69. #endif
  70.     int tt = 1;
  71.     // cin >> tt;
  72.     while (tt--) {
  73.         solve();
  74.     }
  75.     return 0;
  76. }
Success #stdin #stdout 0.01s 10060KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
IMPOSSIBLE
https://ideone.com/UzgPFc
language:
C++ (gcc 8.3)
created:
78 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!