Advertisement
ismaeil

Dijkstra

Aug 6th, 2020
163
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.49 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. typedef long long ll;
  3. using namespace std;
  4.  
  5. typedef pair<ll ,ll> ii;
  6. #define S second
  7. #define F first
  8. #define OO 1e18
  9.  
  10. vector< vector< ii > > AdjList;
  11. int n ,m;
  12.  
  13. void printPath( vector< ll > Parent ,int u){
  14.     if( Parent[u] != u )
  15.         printPath( Parent , Parent[u] );
  16.  
  17.     cout << u << ' ';
  18. }
  19.  
  20. int main() {
  21.     cin >> n >> m;
  22.     AdjList.resize(n + 1);
  23.  
  24.     for(int i=0 ; i<m ; i++){
  25.         int u ,v ,w; cin >> u >> v >> w;
  26.         AdjList[u].push_back( {v,w} );
  27.         AdjList[v].push_back( {u,w} );
  28.     }
  29.  
  30. /// --- \Dijkstra --- ///
  31.     priority_queue< ii , vector< ii > ,greater< ii > > pq;
  32.     vector< ll > Dist(n + 1 ,OO) ,Parent(n + 1);
  33.  
  34.     // parents array : assign to each node => itself
  35.     for(int i = 1 ; i <= n ; i++) Parent[i] = i;
  36.  
  37.     Dist[1] = 0;
  38.     pq.push( {0 ,1} );
  39.     while( !pq.empty() ){
  40.         ii front = pq.top(); pq.pop();
  41.         int u = front.S;
  42.         ll  d = front.F;
  43.  
  44.         if( d > Dist[u] ) continue;
  45.  
  46.         for(int j = 0 ; j < (int)AdjList[u].size() ; j++) {
  47.             ii v = AdjList[u][j];
  48.             if( Dist[u] + v.S < Dist[ v.F ] ) {
  49.                     // Set the parent of the v.F is u = to use it in the path print
  50.                     Parent[ v.F ] = u;
  51.                     Dist[ v.F ] = Dist[ u ] + v.S;
  52.                     pq.push( ii( Dist[ v.F ] ,v.F ) );
  53.             }
  54.         }
  55.     }
  56.  
  57.     if( Dist[n] == OO ) cout << -1 << endl;
  58.     else printPath(Parent ,n);
  59.  
  60.     return 0;
  61. }
  62.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement