fork download
  1. #include <climits>
  2. #include <vector>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <set>
  6.  
  7. #define __DEBUG
  8. #ifdef __DEBUG
  9. #define print_pair(p) do{std::cout << "(" << ((p).first + 1) << ", "\
  10.   << ((p).second + 1) << ")" << std::endl;}while(0);
  11. #endif
  12.  
  13. class Graph
  14. {
  15. private:
  16. std::vector<std::vector<std::pair<int, int>>> adj;
  17. std::vector<int> distances;
  18. std::vector<int> path;
  19. const int INF = INT_MAX;
  20. int vertexes_count = 0, edges_count = 0;
  21. void relax (int start, int end, int length);
  22. public:
  23. typedef std::vector<int> result;
  24. Graph();
  25. Graph(int vertexes, int edges);
  26. ~Graph();
  27. void input();
  28. void output();
  29. result dijkstra(int start);
  30. };
  31.  
  32. Graph::Graph() {}
  33.  
  34. Graph::~Graph() {}
  35.  
  36. Graph::Graph(int vertexes, int edges)
  37. {
  38. vertexes_count = vertexes;
  39. edges_count = edges;
  40. adj.resize(vertexes);
  41. distances.resize(vertexes, INF);
  42. path.resize(vertexes, -1);
  43. }
  44.  
  45. void Graph::input()
  46. {
  47. #ifdef __DEBUG
  48. std::cout << "default distances:" << std::endl;
  49. for (auto &i : distances)
  50. std::cout << i << " ";
  51. std::cout << std::endl;
  52. #endif
  53. int start = 0, end = 0, length = 0;
  54. for (int i = 0; i < edges_count; ++i)
  55. {
  56. std::cin >> start >> end >> length;
  57. adj[start - 1].push_back (std::make_pair(length, end - 1));
  58. }
  59. #ifdef __DEBUG
  60. std::cout << "adjacency lists:" << std::endl;
  61. for (int i = 0; i < adj.size(); ++i)
  62. {
  63. for (int j = 0; j < adj[i].size(); ++j)
  64. {
  65. std::cout << "(" << (i + 1) << ", " << (adj[i][j].second + 1) << ")" << std::endl;
  66. }
  67. std::cout << std::endl;
  68. }
  69. #endif
  70. }
  71.  
  72. Graph::result
  73. Graph::dijkstra (int start)
  74. {
  75. #ifdef __DEBUG
  76. std::cout << "Dijkstra algorithm tracing:" << std::endl;
  77. #endif
  78. distances[start] = 0;
  79. std::set<std::pair<int, int>> q;
  80. q.insert (std::make_pair(distances[start], start));
  81. while (!q.empty())
  82. {
  83. #ifdef __DEBUG
  84. std::cout << "top element of a set: ";
  85. print_pair(*q.begin());
  86. #endif
  87. int current = q.begin()->second;
  88. q.erase(q.begin());
  89. #ifdef __DEBUG
  90. std::cout << "current vertex: " << current << std::endl;
  91. #endif
  92. for (int i = 0; i < adj[current].size(); ++i)
  93. {
  94. #ifdef __DEBUG
  95. std::cout << "current vertex: " << (current + 1);
  96. std::cout << " ad current state of distances array is: " << std::endl;
  97. for (auto i: distances)
  98. std::cout << i << " ";
  99. std::cout << std::endl;
  100. #endif
  101. int to = adj[current][i].second;
  102. int length = adj[current][i].first;
  103. // Relaxations
  104. if (distances[to] > distances[current] + length)
  105. {
  106. #ifdef __DEBUG
  107. std::cout << "relaxation for edge (" << current << ", " << to << ") ";
  108. std::cout << "with weight " << length << std::endl;
  109. #endif
  110.  
  111. q.erase(std::make_pair(distances[to], to));
  112. distances[to] = distances[current] + length;
  113. path[to] = current;
  114. q.insert(std::make_pair(distances[to], to));
  115. }
  116. }
  117. }
  118. // Replace INF by -1
  119. std::replace (distances.begin(), distances.end(), INF, -1);
  120. return distances;
  121. }
  122.  
  123. int main() {
  124. int ntests = 0, nodes = 0, edges = 0, start = 0;
  125. std::cin >> ntests;
  126. for (int i = 0; i < ntests; ++i)
  127. {
  128. std::cin >> nodes >> edges;
  129. Graph g(nodes, edges);
  130. g.input();
  131. std::cin >> start;
  132. auto result = g.dijkstra (start);
  133. for (int j = 0; j < result.size(); ++j)
  134. {
  135. if (j != start)
  136. std::cout << result[i] << " ";
  137. }
  138. std::cout << std::endl;
  139. }
  140. return 0;
  141. }
Success #stdin #stdout 0s 3424KB
stdin
1
4 4
1 2 24
1 4 20
3 1 3
4 3 12
1
stdout
default distances:
2147483647 2147483647 2147483647 2147483647 
adjacency lists:
(1, 2)
(1, 4)


(3, 1)

(4, 3)

Dijkstra algorithm tracing:
top element of a set: (1, 2)
current vertex: 1
-1 -1 -1