fork download
copy 
  1. #include <iostream>
  2. #define FIN "dijkstra.in"
  3. #define FOUT "dijkstra.out"
  4. #include <vector>
  5. #include <queue>
  6. #include <limits>
  7.  
  8. #define MAX_NODES 50005
  9. #define INF std::numeric_limits<int>::max()
  10.  
  11. using namespace std;
  12.  
  13. vector<int> V[MAX_NODES];
  14. vector<int> C[MAX_NODES];
  15. int distMin[MAX_NODES];
  16.  
  17. void readGraph(int& nodes, int& edges) {
  18.     //freopen(FIN, "r", stdin);
  19.     cin >> nodes >> edges;
  20.     for (int edge = 1; edge <= edges; ++edge) {
  21.         int x, y, cost;
  22.         cin >> x >> y >> cost;
  23.         V[x].push_back(y);
  24.         C[x].push_back(cost);
  25.     }
  26. }
  27.  
  28. void dijkstra(int startNode, int nodes) {
  29.     for (int i = 2; i <= nodes; ++i)
  30.         distMin[i] = INF;
  31.     distMin[startNode] = 0;
  32.  
  33.     priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  34.     pq.push({0, startNode});
  35.  
  36.     while (!pq.empty()) {
  37.         int currDist = pq.top().first;
  38.         int currNode = pq.top().second;
  39.         pq.pop();
  40.  
  41.         if (currDist > distMin[currNode]) continue;
  42.  
  43.         for (int i = 0; i < V[currNode].size(); ++i) {
  44.             int nextNode = V[currNode][i];
  45.             int cost = C[currNode][i];
  46.             if (distMin[nextNode] > distMin[currNode] + cost) {
  47.                 distMin[nextNode] = distMin[currNode] + cost;
  48.                 pq.push({distMin[nextNode], nextNode});
  49.             }
  50.         }
  51.     }
  52. }
  53.  
  54. void printShortestDistances(int nodes) {
  55.   //  freopen(FOUT, "w", stdout);
  56.     for (int i = 2; i <= nodes; ++i) {
  57.         cout << (distMin[i] < INF ? distMin[i] : 0) << " ";
  58.     }
  59.     cout << endl;
  60. }
  61.  
  62. int main() {
  63.     int nodes, edges;
  64.     readGraph(nodes, edges);
  65.     dijkstra(1, nodes);
  66.     printShortestDistances(nodes);
  67.     return 0;
  68. }
Success #stdin #stdout 0.01s 5812KB
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/MFrfx7
Dijkstra s algorithm with PQ
language:
C++14 (gcc 8.3)
created:
258 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!