fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4.  
  5. int n, m;
  6. vector<vector<pair<int, int>>> g;
  7. vector<int> dist, par, indegree;
  8.  
  9. int32_t main() {
  10.     ios_base::sync_with_stdio(false);
  11.     cin.tie(NULL);
  12.  
  13.     cin >> n >> m;
  14.     g.resize(n + 1);
  15.     dist.assign(n + 1, LLONG_MIN);
  16.     par.assign(n + 1, -1);
  17.     indegree.assign(n + 1, 0);
  18.  
  19.     for (int i = 0; i < m; ++i) {
  20.         int u, v;
  21.         cin >> u >> v;
  22.         g[u].push_back({v, 1});
  23.         indegree[v]++;
  24.     }
  25.  
  26.     queue<int> q;
  27.  
  28.     for (int i = 1; i <= n; ++i) {
  29.         if (indegree[i] == 0) q.push(i);
  30.     }
  31.  
  32.     dist[1] = 0;
  33.     while (!q.empty()) {
  34.         int u = q.front();
  35.         q.pop();
  36.  
  37.         for (auto [v, w] : g[u]) {
  38.             if (dist[u] != LLONG_MIN && dist[v] < dist[u] + w) {
  39.                 dist[v] = dist[u] + w;
  40.                 par[v] = u;
  41.             }
  42.             indegree[v]--;
  43.             if (indegree[v] == 0) q.push(v);
  44.         }
  45.     }
  46.  
  47.     if (dist[n] == LLONG_MIN) {
  48.         cout << "IMPOSSIBLE\n";
  49.         return 0;
  50.     }
  51.  
  52.     cout << dist[n] + 1 << "\n";
  53.     vector<int> path;
  54.     for (int v = n; v != -1; v = par[v]) {
  55.         path.push_back(v);
  56.     }
  57.     reverse(path.begin(), path.end());
  58.     for (int x : path) cout << x << " ";
  59. }
  60.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
IMPOSSIBLE
https://ideone.com/2XoOda
language:
C++14 (gcc 8.3)
created:
2 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!