fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // INF = very large value (used as initial distance)
  5. const int INF = 1e9;
  6.  
  7. // -------- GLOBAL VARIABLES ---------
  8.  
  9. // graph[u] = list of (neighbor, weight)
  10. vector<vector<pair<int,int>>> graph;
  11.  
  12. // dist[i] = shortest distance from source (0) to node i
  13. vector<int> dist;
  14.  
  15. // parent[i] = previous node of i (for path tracking)
  16. vector<int> parent;
  17.  
  18. // color[i] = state of node
  19. // -1 = unvisited, 0 = processing, 1 = visited
  20. vector<int> color;
  21.  
  22.  
  23. // ------- FUNCTION DECLARATIONS --------
  24. void takeInput(int e);
  25. void dijkstra(int source, int n);
  26. void printPath(int node);
  27. void printResult(int n);
  28.  
  29.  
  30. // -------- MAIN FUNCTION ---------
  31. int main() {
  32.     int nodes, edges;
  33.  
  34.     // input number of nodes and edges
  35.     cin >> nodes >> edges;
  36.  
  37.     // resize all global vectors
  38.     graph.resize(nodes + 1);
  39.     dist.resize(nodes + 1);
  40.     parent.resize(nodes + 1);
  41.     color.resize(nodes + 1);
  42.  
  43.     takeInput(edges);       // input graph
  44.     dijkstra(0, nodes);    // run Dijkstra from source node 0
  45.     printResult(nodes);    // print result
  46.  
  47.     return 0;
  48. }
  49.  
  50.  
  51. // ------ INPUT FUNCTION -------
  52. void takeInput(int e) {
  53.     int u, v, wt;
  54.  
  55.     // read all edges
  56.     for (int i = 0; i < e; i++) {
  57.         cin >> u >> v >> wt;
  58.  
  59.         // store graph (undirected)
  60.         graph[u].push_back({v, wt});
  61.         graph[v].push_back({u, wt});
  62.     }
  63. }
  64.  
  65.  
  66. // ------- DIJKSTRA ALGORITHM --------
  67. void dijkstra(int source, int n) {
  68.  
  69.     // min-heap (priority queue)
  70.     priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
  71.  
  72.     // initialize all nodes
  73.     for (int i = 0; i <= n; i++) {
  74.         dist[i] = INF;      // initially distance = infinity
  75.         parent[i] = -1;     // no parent
  76.         color[i] = -1;      // unvisited
  77.     }
  78.  
  79.     // start from source
  80.     dist[source] = 0;
  81.     pq.push({0, source});
  82.     color[source] = 0; // processing
  83.  
  84.     // main loop
  85.     while (!pq.empty()) {
  86.  
  87.         int u = pq.top().second;
  88.         pq.pop();
  89.  
  90.         // if already visited, skip
  91.         if (color[u] == 1) continue;
  92.  
  93.         color[u] = 1; // mark visited
  94.  
  95.         // check all neighbors of u
  96.         for (auto edge : graph[u]) {
  97.             int v = edge.first;
  98.             int wt = edge.second;
  99.  
  100.             // if neighbor not visited before
  101.             if (color[v] == -1) {
  102.                 color[v] = 0; // mark as processing
  103.             }
  104.  
  105.             // relaxation step (main Dijkstra logic)
  106.             if (dist[u] + wt < dist[v]) {
  107.                 dist[v] = dist[u] + wt; // update distance
  108.                 parent[v] = u;          // store parent for path
  109.                 pq.push({dist[v], v});
  110.             }
  111.         }
  112.     }
  113. }
  114.  
  115.  
  116. // ------ PRINT PATH --------
  117. // Recursively prints path from source (0) to node
  118. void printPath(int node) {
  119.  
  120.     if (node == -1) return;
  121.  
  122.     // first print parent path
  123.     if (parent[node] != -1) {
  124.         printPath(parent[node]);
  125.         cout << " → ";
  126.     }
  127.  
  128.     // then print current node
  129.     cout << node;
  130. }
  131.  
  132.  
  133. // ------ PRINT RESULT --------
  134. void printResult(int n) {
  135.  
  136.     for (int i = 1; i <= n; i++) {
  137.  
  138.         cout << "Customer " << i << ": ";
  139.  
  140.         // if unreachable
  141.         if (dist[i] == INF) {
  142.             cout << "Not reachable\n";
  143.         } 
  144.         else {
  145.             cout << "Minimum Distance = " << dist[i] << ", Path = ";
  146.             printPath(i);   // print path
  147.             cout << "\n";
  148.         }
  149.     }
  150. }
Success #stdin #stdout 0s 5308KB
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 = 0 → 2 → 1
Customer 2: Minimum Distance = 3, Path = 0 → 2
Customer 3: Minimum Distance = 6, Path = 0 → 2 → 1 → 3
Customer 4: Not reachable
https://ideone.com/mxKLyR
language:
C++ (gcc 8.3)
created:
5 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!