fork download
copy 
  1. #include <climits>
  2. #include <vector>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <queue>
  6.  
  7. class Graph
  8. {
  9. private:
  10.     struct node
  11.     {
  12.         int vertex, length;
  13.         bool operator < (const node &x) const
  14.         {
  15.             return length > x.length;
  16.         }
  17.     };
  18.  
  19.     std::vector<std::vector<std::pair<int, int>>> adj;
  20.     std::vector<int> distances;
  21.     std::vector<int> path;
  22.  
  23.     const int INF = INT_MAX;
  24.     int vertexes_count = 0, edges_count = 0;
  25.  
  26.     void relax (int start, int end, int length);
  27. public:
  28.     typedef std::vector<int> result;
  29.     Graph();
  30.     Graph(int vertexes, int edges);
  31.     ~Graph();
  32.     void input();
  33.     void output();
  34.     result dijkstra(int start);
  35. };
  36.  
  37. Graph::Graph() {}
  38.  
  39. Graph::~Graph() {}
  40.  
  41. Graph::Graph(int vertexes, int edges)
  42. {
  43.     vertexes_count = vertexes;
  44.     edges_count    = edges;
  45.     adj.resize(vertexes + 1);
  46.     distances.resize(vertexes + 1, INF);
  47.     path.resize(vertexes + 1, -1);
  48. }
  49.  
  50. void Graph::input()
  51. {
  52.     int start = 0, end = 0, length = 0;
  53.     for (int i = 0; i < edges_count; ++i)
  54.     {
  55.         std::cin >> start >> end >> length;
  56.         adj[start].push_back (std::make_pair(end, length));
  57.         adj[end].push_back (std::make_pair(start, length));
  58.     }
  59. }
  60.  
  61. Graph::result
  62. Graph::dijkstra (int start)
  63. {
  64.     distances[start] = 0;
  65.     path[start] = start;
  66.     std::priority_queue<node> q;
  67.     q.push({start, 0});
  68.     while (!q.empty())
  69.     {
  70.         int current = q.top().vertex;
  71.         q.pop();
  72.         for (int i = 0; i < adj[current].size(); ++i)
  73.         {
  74.             int to     = adj[current][i].first;
  75.             int length = adj[current][i].second;
  76.             // Relaxations
  77.             if (distances[to] > distances[current] + length)
  78.             {
  79.                 path[to] = current;     
  80.                 distances[to] = distances[current] + length;
  81.                 q.push({to, distances[to]});
  82.             }
  83.         }
  84.     }
  85.     // Replace INF by -1
  86.     std::replace (distances.begin(), distances.end(), INF, -1);
  87.     return distances;
  88. }
  89.  
  90. int main() {
  91.     int ntests = 0, nodes = 0, edges = 0, start = 0;
  92.     std::cin >> ntests;
  93.     for (int i = 0; i < ntests; ++i)
  94.     {
  95.         std::cin >> nodes >> edges;
  96.         Graph g(nodes, edges);
  97.         g.input();
  98.         std::cin >> start;
  99.         Graph::result result = g.dijkstra (start);
  100.         for (int j = 1; j < result.size(); ++j)
  101.         {
  102.             if (j != start)
  103.                 std::cout << result[j] << " ";
  104.         }
  105.         std::cout << std::endl;
  106.     }
  107.     return 0;
  108. }
Success #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
1
4 4
1 2 24
1 4 20
3 1 3
4 3 12
1
stdout
copy 
24 3 15
https://ideone.com/FhnKiV
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!