fork download
copy 
  1. #include <cstdio>
  2. #include <vector>
  3. #include <queue>
  4. #include <bitset>
  5. #define MAXN 50005
  6. #define oo ((1LL<<31)-1)
  7. #define FIN "dijkstra.in"
  8. #define FOUT "dijkstra.out"
  9.  
  10. using namespace std;
  11.  
  12. vector<int> V[ MAXN ];
  13. vector<int> C[ MAXN ];
  14. int distMin[ MAXN ];
  15. queue<int> Queue;
  16. bitset<MAXN> inQueue(0);
  17.  
  18. int nodes,
  19.     edges;
  20.  
  21. //prototpes functions
  22. void readData();
  23. void Dijkstra();
  24. void writeData();
  25. void printV();
  26.  
  27. //main function
  28. int main() {
  29.  
  30.     readData();
  31.     Dijkstra();
  32.     writeData();
  33.  
  34.     return(0);
  35. };
  36.  
  37. void readData() {
  38.  
  39.      int x,
  40.          y,
  41.          cost;
  42.  
  43.      //freopen(FIN, "r", stdin);
  44.  
  45.      scanf("%d %d", &nodes, &edges);
  46.  
  47.      for(int ed = 1; ed <= edges; ed++) {
  48.  
  49.          scanf("%d %d %d", &x, &y, &cost);
  50.  
  51.          V[ x ].push_back( y ); 
  52.          C[ x ].push_back( cost ); 
  53.      }
  54.  
  55.      fclose( stdin );
  56. };
  57.  
  58. void Dijkstra() {
  59.  
  60.      for(int i = 2; i <= nodes; i++) distMin[ i ] = oo;
  61.  
  62.      distMin[ 1 ] = 0;
  63.  
  64.      Queue.push( 1 );
  65.  
  66.      inQueue[ 1 ] = true;
  67.  
  68.      while(!Queue.empty()) {
  69.  
  70.             int curr = Queue.front();
  71.  
  72.             Queue.pop();
  73.  
  74.             inQueue[ curr ] = false;    
  75.  
  76.             for(int i = 0; i < V[ curr ].size(); i++) {
  77.  
  78.                     int y = V[ curr ][ i ];
  79.  
  80.                     int cost = C[ curr ][ i ];
  81.  
  82.                     if(distMin[ y ] > distMin[ curr ] + cost) {
  83.  
  84.                        distMin[ y ] = distMin[ curr ] + cost;
  85.  
  86.                        if(!inQueue[ y ]) {
  87.  
  88.                            Queue.push( y );
  89.  
  90.                            inQueue[ y ] = true;
  91.                        }
  92.  
  93.                     }
  94.             } 
  95.      }
  96. };
  97.  
  98. void writeData() {
  99.  
  100.      //freopen(FOUT, "w", stdout);
  101.  
  102.      for(int i = 2; i <= nodes; i++) printf("%d ", (distMin[ i ] < oo) ? distMin[ i ] : 0);
  103.  
  104.      fclose( stdout );
  105. };
Success #stdin #stdout 0.01s 5540KB
comments (?)
stdin
copy 
5 6
1 2 1
1 4 2
4 3 4
2 3 2
4 5 3
3 5 6
stdout
copy 
1 3 2 5
https://ideone.com/vc0dRN
Dijkstra's algorithm
language:
C++14 (gcc 8.3)
created:
246 days ago
visibility:
secret

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!