fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int INF = 1e9;
  5.  
  6. // Global declarations
  7. vector<vector<pair<int, int>>> graph;
  8. vector<int> dist;
  9. vector<int> parent;
  10.  
  11. // Function declarations
  12. void takeInput(int e);
  13. void dijkstra(int source, int n);
  14. void printPath(int node);
  15. void printResult(int n);
  16.  
  17. int main() {
  18.     int nodes, edges;
  19.     cin >> nodes >> edges;
  20.  
  21.     graph.resize(nodes + 1);
  22.     dist.resize(nodes + 1);
  23.     parent.resize(nodes + 1);
  24.  
  25.     takeInput(edges);
  26.     dijkstra(0, nodes);
  27.     printResult(nodes);
  28.  
  29.     return 0;
  30. }
  31.  
  32. // Input graph
  33. void takeInput(int e) {
  34.     int u, v, wt;
  35.  
  36.     for (int i = 0; i < e; i++) {
  37.         cin >> u >> v >> wt;
  38.         graph[u].push_back({v, wt});
  39.         graph[v].push_back({u, wt});
  40.     }
  41. }
  42.  
  43. // Dijkstra Algorithm
  44. void dijkstra(int source, int n) {
  45.     priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  46.  
  47.     for (int i = 0; i <= n; i++) {
  48.         dist[i] = INF;
  49.         parent[i] = -1;
  50.     }
  51.  
  52.     dist[source] = 0;
  53.     pq.push({0, source});
  54.  
  55.     while (!pq.empty()) {
  56.         int u = pq.top().second;
  57.         pq.pop();
  58.  
  59.         for (auto edge : graph[u]) {
  60.             int v = edge.first;
  61.             int wt = edge.second;
  62.  
  63.             if (dist[u] + wt < dist[v]) {
  64.                 dist[v] = dist[u] + wt;
  65.                 parent[v] = u;
  66.                 pq.push({dist[v], v});
  67.             }
  68.         }
  69.     }
  70. }
  71.  
  72. // Print shortest path
  73. void printPath(int node) {
  74.     if (node == -1) return;
  75.  
  76.     printPath(parent[node]);
  77.     cout << node;
  78.  
  79.     if (parent[node] != -1)
  80.         cout << " -> ";
  81. }
  82.  
  83. // Print final result
  84. void printResult(int n) {
  85.     for (int i = 1; i <= n; i++) {
  86.         cout << "Customer " << i << ": ";
  87.  
  88.         if (dist[i] == INF) {
  89.             cout << "Not reachable" << endl;
  90.         } 
  91.         else {
  92.             cout << "Minimum Distance = " << dist[i] << ", Path = ";
  93.             printPath(i);
  94.             cout << endl;
  95.         }
  96.     }
  97. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
4 5
0 1 10
0 2 3
1 2 1
1 3 2
2 3 8
stdout
copy 
Customer 1: Minimum Distance = 4, Path = 02 -> 1 -> 
Customer 2: Minimum Distance = 3, Path = 02 -> 
Customer 3: Minimum Distance = 6, Path = 02 -> 1 -> 3 -> 
Customer 4: Not reachable
https://ideone.com/ai7dJs
language:
C++ (gcc 8.3)
created:
8 hours 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!