Problem 38: Dijkstra's Shortest Path
Problem Statement: Given a weighted directed graph with n nodes and m edges, and a source node 1, compute the shortest distance from node 1 to every other node. If a node is unreachable, print -1 for that node.
Input
The first line contains two integers n and m. Each of the next m lines contains three integers u, v, and w representing an edge from u to v with weight w.
Output
Print n space-separated integers representing the shortest distances from node 1 to each node (1-indexed).
Examples
Input:
5 6
1 2 2
1 3 4
2 3 1
2 4 7
3 5 3
4 5 1
Output:
0 2 3 9 6
Solution in C++
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m; cin >> n >> m;
vector<vector<pair<int, int>>> adj(n+1);
for(int i = 0; i < m; i++){
int u, v, w; cin >> u >> v >> w;
adj[u].push_back({v, w});
}
vector<ll> dist(n+1, INF);
dist[1] = 0;
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>>pq;
pq.push({0, 1});
while(!pq.empty()){
auto [d, u] = pq.top(); pq.pop();
if(d != dist[u]) continue;
for(auto &edge: adj[u]){
int v = edge.first;
int w = edge.second;
if(dist[u] + w < dist[v]){
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
for(int i = 1; i <= n; i++){
cout << (dist[i] == INF ? -1 : dist[i]) << " ";
}
cout << "\n";
return 0;
}