Guest User

Untitled

a guest
Jan 4th, 2023
229
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.24 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define endl "\n"
  3. using namespace std;
  4. #define int long long int
  5.  
  6.  
  7. int n, m;
  8. vector<vector<pair<int,int>>> g;
  9. vector<int> dist;
  10. vector<int> par;
  11.  
  12. void dij()
  13. {
  14.     priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
  15.     pq.push({0,1});
  16.     dist[1] = 0;
  17.     par[1] = -1;
  18.  
  19.     while(!pq.empty())
  20.     {
  21.         int u = pq.top().second;
  22.         int d = pq.top().first;
  23.         pq.pop();
  24.        
  25.         if(dist[u] < d) continue;
  26.        
  27.         for(auto e: g[u])
  28.         {
  29.             int v = e.first;
  30.             int c = e.second;
  31.             if(dist[v] > dist[u]+c)
  32.             {
  33.                 dist[v] = dist[u]+c;
  34.                 pq.push({dist[v],v});
  35.                 par[v] = u;
  36.             }
  37.         }
  38.  
  39.  
  40.     }
  41.  
  42. }
  43.  
  44. int32_t main()
  45. {
  46.     ios_base::sync_with_stdio(false);
  47.     cin.tie(NULL);
  48.     cin >> n >> m;
  49.     dist.resize(n+1);
  50.     par.resize(n+1);
  51.    
  52.     for(int i = 1; i <= n; ++i)
  53.     {
  54.         par[i] = -1;
  55.     }
  56.  
  57.     g.resize(n+1);
  58.     for(int i = 0; i < m; ++i)
  59.     {
  60.         int u, v;
  61.         cin >> u >> v;
  62.         g[u].push_back({v,-1});
  63.     }
  64.     dij();
  65.     if(dist[n] == 0)
  66.     {
  67.         cout << "IMPOSSIBLE";
  68.         return 0;
  69.     }
  70.    
  71.     cout << 1 + dist[n]*(-1) << endl;
  72.     vector<int> ans;
  73.     int temp = n;
  74.     while(temp != -1)
  75.     {
  76.         ans.push_back(temp);
  77.         temp = par[temp];
  78.     }
  79.     reverse(ans.begin(), ans.end());
  80.     for(auto u: ans)
  81.     {
  82.         cout << u << " ";
  83.     }
  84.  
  85. }
Advertisement
Add Comment
Please, Sign In to add comment