fork download
  1. #include <vector>
  2. #include <iostream>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. class Graph
  8. {
  9. private:
  10. // Pair: (ending vertex, weigth)
  11. vector<vector<pair<int, int>>> adj_list;
  12. int nodes, edges;
  13. public:
  14. Graph() = default;
  15. Graph(int nodes, int edges);
  16. Graph(int nodes, int edges, istream &is);
  17. ~Graph(){}
  18. void print_edges();
  19. std::vector<int> dijkstra(int);
  20. };
  21.  
  22. Graph::Graph (int nodes, int edges)
  23. {
  24. adj_list.resize (nodes + 1);
  25. this->nodes = nodes;
  26. this->edges = edges;
  27. }
  28.  
  29. Graph::Graph(int nodes, int edges, istream &is) : Graph(nodes, edges)
  30. {
  31. int begin = 0, end = 0, weigth = 0;
  32. for (size_t i = 0; i < edges; ++i)
  33. {
  34. is >> begin >> end >> weigth;
  35. adj_list[begin].push_back (make_pair(end, weigth));
  36. adj_list[end].push_back (make_pair(begin, weigth));
  37. }
  38. }
  39.  
  40. void Graph::print_edges()
  41. {
  42. for (size_t i = 0; i < adj_list.size(); ++i)
  43. {
  44. for (size_t j = 0; j < adj_list[i].size(); ++j)
  45. {
  46. cout << "(" << i << ", " << adj_list[i][j].first << ")"; // (i, j)
  47. cout << " ";
  48. }
  49. cout << endl;
  50. }
  51. }
  52.  
  53. std::vector<int> Graph::dijkstra(int start)
  54. {
  55. const int INF = 1000000000;
  56. vector<int> distance (nodes + 1, INF);
  57. vector<bool> visited (nodes + 1);
  58.  
  59. distance[start] = 0;
  60. for (int i = 1; i <= nodes; ++i)
  61. {
  62. // Find a vertex with minimal mark
  63. int minimum = INF;
  64. int current = 0;
  65. for (int j = 1; j <= nodes; ++j)
  66. {
  67. if (distance[j] < minimum && !visited[j])
  68. {
  69. minimum = distance[j];
  70. current = j;
  71. }
  72. }
  73. // Mark minimal node as visited
  74. visited[current] = true;
  75. // Relaxations
  76. for (int i = 0; i < adj_list[current].size(); ++i)
  77. {
  78. int to = adj_list[current][i].first;
  79. int weigth = adj_list[current][i].second;
  80. distance[to] = std::min (distance[to], distance[current] + weigth);
  81. }
  82. }
  83.  
  84. return distance;
  85. }
  86.  
  87. int main() {
  88. int tests = 0, nodes = 0, edges = 0, start = 0;
  89. cin >> tests;
  90.  
  91. for (int i = 0; i < tests; ++i)
  92. {
  93. cin >> nodes >> edges;
  94. Graph g(nodes, edges, cin);
  95. cin >> start;
  96. auto result = g.dijkstra (start);
  97. for (int i = 1; i < result.size(); ++i)
  98. {
  99. if (i != start)
  100. cout << result[i] << " ";
  101. }
  102. std::cout << std::endl;
  103. }
  104. return 0;
  105. }
Success #stdin #stdout 0s 3468KB
stdin
1
20 54
1 7 45
2 14 15
3 7 29
4 1 48
5 1 66
6 7 17
7 14 15
8 14 43
9 1 27
10 1 33
11 14 64
12 14 27
13 7 66
14 7 54
15 14 56
16 7 21
17 1 20
18 1 34
19 7 52
20 14 14
9 14 9
15 1 39
12 1 24
9 1 16
1 2 33
18 1 46
9 1 28
15 14 3
12 1 27
1 2 5
15 1 34
1 2 28
9 7 16
3 7 23
9 7 21
9 14 19
3 1 20
3 1 5
12 14 19
3 14 2
12 1 46
3 14 5
9 14 44
6 14 26
9 14 16
9 14 34
6 7 42
3 14 27
1 7 9
1 7 41
15 14 19
12 7 13
3 7 10
1 7 2
17
stdout
20 25 25 68 86 39 22 70 36 53 91 35 88 27 30 43 54 74 41