UAIC Competitive Programming

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 Explanation

Method 1: Use Dijkstra's algorithm with a priority queue to efficiently compute the shortest path distances from the source to all nodes. Method 2: For smaller graphs, you could use a simple O(n^2) approach by repeatedly selecting the unvisited node with the smallest distance, but Dijkstra's algorithm with a min-heap is preferred for efficiency.

Solution in C++


#include 
#include 
#include 
#include 
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>> 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 dist(n+1, INF);
    dist[1] = 0;
    priority_queue, vector>, greater>>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 << "
";
    return 0;
}