fork download
copy 
  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.     }
  37. }
  38.  
  39. void Graph::print_edges()
  40. {
  41.     for (size_t i = 0; i < adj_list.size(); ++i)
  42.     {
  43.         for (size_t j = 0; j < adj_list[i].size(); ++j)
  44.         {
  45.             cout << "(" << i << ", " << adj_list[i][j].first << ")";   // (i, j)
  46.             cout << " ";
  47.         }
  48.         cout << endl;
  49.     }
  50. }
  51.  
  52. std::vector<int> Graph::dijkstra(int start)
  53. {
  54.     const int INF = 1000000000;
  55.     vector<int>  distance (nodes + 1, INF);
  56.     vector<bool> visited (nodes + 1);
  57.  
  58.     distance[start] = 0;
  59.     for (int i = 1; i <= nodes; ++i)
  60.     {
  61.         // Find a vertex with minimal mark
  62.         int minimum = INF;
  63.         int current = 0;
  64.         for (int j = 1; j <= nodes; ++j)
  65.         {
  66.             if (distance[j] < minimum && !visited[j])
  67.             {
  68.                 minimum = distance[j];
  69.                 current = j;
  70.             }
  71.         }
  72.         // Mark minimal node as visited
  73.         visited[current] = true;
  74.         // Relaxations
  75.         for (int i = 0; i < adj_list[current].size(); ++i)
  76.         {
  77.             int to     = adj_list[current][i].first;
  78.             int weigth = adj_list[current][i].second;
  79.             distance[to] = std::min (distance[to], distance[current] + weigth);
  80.         }
  81.     }
  82.  
  83.     return distance;
  84. }
  85.  
  86. int main() {
  87.     int tests = 0, nodes = 0, edges = 0, start = 0;
  88.     cin >> tests;
  89.  
  90.     for (int i = 0; i < tests; ++i)
  91.     {
  92.         cin >> nodes >> edges;
  93.         Graph g(nodes, edges, cin);
  94.         cin >> start;
  95.         auto result = g.dijkstra (start);
  96.         for (int i = 1; i < result.size(); ++i)
  97.         {
  98.             if (i != start)
  99.                 cout << result[i] << " ";
  100.         }
  101.         std::cout << endl;
  102.     }
  103.     return 0;
  104. }
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 
24 32 20
https://ideone.com/eGhmMK
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!