fork download
copy 
  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
comments (?)
stdin
copy 
1
4 4
1 2 24
1 4 20
3 1 3
4 3 12
1
stdout
copy 
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
https://ideone.com/gOgS0z
language:
C++14 (gcc 8.3)
created:
8 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!