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>>> graph;
  20.     std::vector<int> distance;
  21.  
  22.     const int INF = INT_MAX;
  23.     int vertexes_count = 0, edges_count = 0;
  24. public:
  25.     typedef std::vector<int> result;
  26.     Graph();
  27.     Graph(int vertexes, int edges);
  28.     ~Graph();
  29.     void input();
  30.     result dijkstra(int start);
  31. };
  32.  
  33. Graph::Graph() {}
  34.  
  35. Graph::~Graph() {}
  36.  
  37. Graph::Graph(int vertexes, int edges)
  38. {
  39.     vertexes_count = vertexes;
  40.     edges_count    = edges;
  41.     graph.resize(vertexes + 1);
  42.     distance.resize(vertexes + 1, INF);
  43. }
  44.  
  45. void Graph::input()
  46. {
  47.     int start = 0, end = 0, length = 0;
  48.     for (int i = 0; i < edges_count; ++i)
  49.     {
  50.         std::cin >> start >> end >> length;
  51.         graph[start].push_back (std::make_pair(end, length));
  52.         graph[end].push_back (std::make_pair(start, length));
  53.     }
  54. }
  55.  
  56. Graph::result
  57. Graph::dijkstra (int start)
  58. {
  59.     distance[start] = 0;
  60.  
  61.     std::priority_queue<node> q;
  62.  
  63.     q.push({start, 0});
  64.  
  65.     while (!q.empty())
  66.     {
  67.         int current = q.top().vertex;
  68.         q.pop();
  69.  
  70.         for (auto &adjacent : graph[current])
  71.         {
  72.             int to     = adjacent.first;
  73.             int length = adjacent.second;
  74.             // Relaxations
  75.             if (distance[to] > distance[current] + length)
  76.             {    
  77.                 distance[to] = distance[current] + length;
  78.                 q.push({to, distance[to]});
  79.             }
  80.         }
  81.     }
  82.     // Replace INF by -1
  83.     std::replace (distance.begin(), distance.end(), INF, -1);
  84.     return distance;
  85. }
  86.  
  87. int main() {
  88.     int ntests = 0, nodes = 0, edges = 0, start = 0;
  89.     std::cin >> ntests;
  90.     for (int i = 0; i < ntests; ++i)
  91.     {
  92.         std::cin >> nodes >> edges;
  93.         Graph g(nodes, edges);
  94.         g.input();
  95.         std::cin >> start;
  96.         auto result = g.dijkstra (start);
  97.         for (int j = 1; j < result.size(); ++j)
  98.         {
  99.             if (j != start)
  100.                 std::cout << result[j] << " ";
  101.         }
  102.         std::cout << std::endl;
  103.     }
  104.     return 0;
  105. }
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/O1ziGq
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!