fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. // Maximum number of nodes
  7. const int MaxN = 1 + 1e2;
  8. // Infinite distance used to represent unreachable nodes
  9. const ll INF = 1e18;
  10.  
  11. int n, m, s; // n = number of nodes, m = number of edges, s = source node
  12. bool mark[MaxN]; // mark array to check if a node has been processed
  13. ll dist[MaxN]; // Array to store the shortest distance from the source to each node
  14. vector<pair<int, int>> adj[MaxN]; // Adjacency list to store the graph. Each pair represents (destination node, edge weight)
  15.  
  16. void Dijkstra(int s){
  17.     // Initialize all distances as INF (unreachable), except the source node which is 0
  18.     fill(dist + 1, dist + n + 1, INF);
  19.     dist[s] = 0; // Distance to the source node is always 0
  20.  
  21.     // Priority queue (min-heap) for selecting the node with the smallest distance
  22.     // The pair consists of (distance, node)
  23.     priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll,int>>> pq;
  24.     pq.push({0, s}); // Push the source node with distance 0 into the priority queue
  25.  
  26.     while(!pq.empty()){
  27.         int u = pq.top().second; // Get the node with the smallest distance
  28.         pq.pop();
  29.  
  30.         // If the node is already processed, skip it
  31.         if(mark[u]) continue;
  32.         mark[u] = true; // Mark the node as processed
  33.  
  34.         // Process all neighbors of the current node
  35.         for(auto e : adj[u]){
  36.             int v = e.first; // Neighbor node
  37.             ll w = e.second; // Weight of the edge connecting u and v
  38.  
  39.             // If the new distance through node u is shorter, update the distance to node v
  40.             if(dist[v] > dist[u] + w){
  41.                 dist[v] = dist[u] + w; // Update the shortest distance to node v
  42.                 pq.push({dist[v], v}); // Push the updated distance and node into the priority queue
  43.             }
  44.         }
  45.     }
  46. }
  47.  
  48. int main(){
  49.     // Read number of nodes, edges, and the source node
  50.     cin >> n >> m >> s;
  51.  
  52.     // Read the edges (u, v, w) and populate the adjacency list
  53.     for(int i = 0; i < m; ++i){
  54.         int u, v, w;
  55.         cin >> u >> v >> w;
  56.         adj[u].push_back({v, w}); // Add the edge u -> v with weight w to the adjacency list
  57.     }
  58.  
  59.     // Run Dijkstra's algorithm to find the shortest path from source s
  60.     Dijkstra(s);
  61.  
  62.     // Print the shortest distances to all nodes from the source
  63.     for(int i = 1; i <= n; ++i){
  64.         // If a node is unreachable (distance is INF), print -1
  65.         if(dist[i] == INF) cout << -1 << endl;
  66.         else cout << dist[i] << endl; // Otherwise, print the shortest distance
  67.     }
  68.  
  69.     return 0;
  70. }
  71.  
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
7 8 1
1 2 4
1 3 5
1 4 2
4 2 1
4 6 4
3 5 3
6 5 1
1 5 8
stdout
copy 
0
3
5
2
7
6
-1
https://ideone.com/FGsAht
Problem Description: Given a directed graph with n vertices (numbered from 1 to n) and m directed edges with non-negative integer weights, and a starting vertex s, find the shortest path lengths from vertex s to all other vertices. If there is no path between two vertices, print -1.
language:
C++ (gcc 8.3)
created:
1 day 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!