fork download 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <bitset>
  5. #include <deque>
  6. #include <queue>
  7. using namespace std;
  8.  
  9. ifstream fin("dijkstra.in");
  10. ofstream fout("dijkstra.out");
  11.  
  12. const int MAX_NODES = 50000;
  13. const long long MAX_DISTANCE = 5000000000;
  14.  
  15. vector<pair<int, int>> graph[MAX_NODES + 1];
  16.  
  17. priority_queue<int> currentNodes;
  18.  
  19. pair<int, int> arch;
  20.  
  21. long long minDistance[MAX_NODES + 1];
  22.  
  23. int main() {
  24.     int noNodes, noArches;
  25.     cin >> noNodes >> noArches;
  26.     for (int i = 1; i <= noArches; ++i) {
  27.         int startNode;
  28.        // pair<int, int> arch;
  29.         cin >> startNode >> arch.first >> arch.second;
  30.         minDistance[i] = MAX_DISTANCE + 1;
  31.         graph[startNode].push_back(arch);
  32.     }
  33.     minDistance[1] = 0;
  34.     currentNodes.push(1);
  35.     while (currentNodes.empty() == 0) {
  36.         int startNode = currentNodes.top();
  37.         currentNodes.pop();
  38.         for (vector<pair<int, int>>::iterator it = graph[startNode].begin(); it < graph[startNode].end(); ++it) {
  39.             if (minDistance[startNode] + it->second < minDistance[it->first]) {
  40.                 minDistance[it->first] = minDistance[startNode] + it->second;
  41.                 currentNodes.push(it->first);
  42.             }
  43.         }
  44.     }
  45.    // currentNodes.push_back(1);
  46.    /* while (currentNodes.size() > 0) {
  47.         for (deque<int>::iterator it = currentNodes.begin(); it < currentNodes.end(); ++it) {
  48.             for (vector<pair<int, int>>::iterator it2 = graph[*it].begin(); it2 < graph[*it].end(); ++it2) {
  49.                 if (minDistance[*it] + it2->second < minDistance[it2->first]) {
  50.                     minDistance[it2->first] = minDistance[*it] + it2->second;
  51.                     nextNodes.push_back(it2->first);
  52.                 }
  53.             }
  54.         }
  55.         currentNodes = nextNodes;
  56.         nextNodes.clear();
  57.     }*/
  58.  
  59.     for (int i = 2; i <= noNodes; ++i) {
  60.         if (minDistance[i] == MAX_DISTANCE + 1) {
  61.             minDistance[i] = 0;
  62.         }
  63.         cout << minDistance[i] << ' ';
  64.     }
  65.     return 0;
  66. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin 
5 6
 1 2 1
 1 4 2
 4 3 4
 2 3 2
 4 5 3
 3 5 6
stdout 
1 3 2 5
https://ideone.com/CPGcZ9
language:
C++ (gcc 8.3)
created:
2 years 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!