Hard
CPP-004cppShortest Path (Dijkstra)
Problem
Given a weighted graph, find shortest path from source to every node using Dijkstra's algorithm.
Input
Line 1: n m source. Next m lines: `u v w` (1-indexed, non-negative weight).
Output
n lines: distance from source to i (or -1 if unreachable).
Constraints
1 ≤ n ≤ 10^5, 1 ≤ m ≤ 5·10^5, 0 ≤ w ≤ 10^6
Sample input
4 5 1 1 2 1 2 3 2 1 3 4 3 4 1 2 4 5
Sample output
0 1 3 4
Explanation
Shortest: 1→2 (1), 1→2→3 (3), 1→2→3→4 (4).
graphsdijkstrapriority-queue@Google@Uber@Flipkart
Visible test cases
in: 4 5 1 1 2 1 2 3 2 1 3 4 3 4 1 2 4 5
out: 0 1 3 4
Your solution — run it, use AI if stuck
cpp