fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int INF = 1e9;
  5.  
  6. // ---------------------- Graph Input ----------------------
  7. void takeInput(int &N, int &E, vector<vector<pair<int,int>>> &graph) {
  8.     cin >> N >> E;
  9.  
  10.     graph.assign(N + 1, {});
  11.  
  12.     for (int i = 0; i < E; i++) {
  13.         int u, v, w;
  14.         cin >> u >> v >> w;
  15.  
  16.         graph[u].push_back({v, w});
  17.         graph[v].push_back({u, w}); // remove if directed
  18.     }
  19. }
  20.  
  21. // ---------------------- Dijkstra Algorithm ----------------------
  22. void dijkstra(int source,
  23.               vector<vector<pair<int,int>>> &graph,
  24.               vector<int> &dist,
  25.               vector<int> &parent) {
  26.  
  27.     int n = graph.size();
  28.     dist.assign(n, INF);
  29.     parent.assign(n, -1);
  30.  
  31.     priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
  32.  
  33.     dist[source] = 0;
  34.     pq.push({0, source});
  35.  
  36.     while (!pq.empty()) {
  37.         auto [currentDist, u] = pq.top();
  38.         pq.pop();
  39.  
  40.         if (currentDist > dist[u]) continue;
  41.  
  42.         for (auto [v, weight] : graph[u]) {
  43.             if (dist[u] + weight < dist[v]) {
  44.                 dist[v] = dist[u] + weight;
  45.                 parent[v] = u;
  46.                 pq.push({dist[v], v});
  47.             }
  48.         }
  49.     }
  50. }
  51.  
  52. // ---------------------- Path Printing ----------------------
  53. void printPath(int node, vector<int> &parent) {
  54.     if (node == -1) return;
  55.     printPath(parent[node], parent);
  56.     cout << node;
  57.     if (parent[node] != -1) cout << " -> ";
  58. }
  59.  
  60. // ---------------------- Output ----------------------
  61. void printResult(int N, vector<int> &dist, vector<int> &parent) {
  62.     for (int i = 1; i <= N; i++) {
  63.         cout << "Customer " << i << ": ";
  64.  
  65.         if (dist[i] == INF) {
  66.             cout << "Not reachable\n";
  67.         } else {
  68.             cout << "Minimum Distance = " << dist[i] << ", Path = ";
  69.             printPath(i, parent);
  70.             cout << "\n";
  71.         }
  72.     }
  73. }
  74.  
  75. // ---------------------- Main ----------------------
  76. int main() {
  77.     int N, E;
  78.     vector<vector<pair<int,int>>> graph;
  79.  
  80.     // Step 1: Input
  81.     takeInput(N, E, graph);
  82.  
  83.     // Step 2: Dijkstra
  84.     vector<int> dist, parent;
  85.     dijkstra(0, graph, dist, parent); // source = 0
  86.  
  87.     // Step 3: Output
  88.     printResult(N, dist, parent);
  89.  
  90.     return 0;
  91. }
Success #stdin #stdout 0.01s 5288KB
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/FmMhDx
language:
C++ (gcc 8.3)
created:
10 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!