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