Dijkstra Algorithm

Practice this coding question on Coding Gurukul.

Problem statement

Given a directed weighted graph and source s, use Dijkstra’s algorithm to find the shortest distance from s to every vertex. All edge weights are nonnegative. Print distances in vertex order. The distance to s is 0. Print -1 for an unreachable vertex. An edge u v w goes from u to v only. Zero-weight edges, self-loops and repeated edges are allowed. Use a min-priority queue, signed 64-bit distances, and O((n+m) log n) time. Worked example The path 0→2→1 costs 2+3=5, less than the direct edge of weight 9. Distances from 0 are 0, 5, 2 and -1; vertex 3 is unreachable.

Input format

First line: n m s. Next m lines: u v w.

Output format

Print n distances in vertex order 0 to n-1, using -1 for unreachable vertices.

Constraints

1 <= n <= 100000; 0 <= m <= 200000; 0 <= s,u,v < n; 0 <= w <= 10^9.

Sample input

4 3 0
0 1 9
0 2 2
2 1 3

Sample output

0 5 2 -1

Sign in to run or submit a solution in C++, Java or Python.