Single Source Shortest Path - Dijkstra's Algorithm

Given a weighted directed graph with \(n\) nodes and \(m\) edges, you are required to compute the shortest path distances from a given start node \(s\) to every other node using Dijkstra's algorithm. The nodes are numbered from 1 to \(n\). For nodes that are not reachable from \(s\), output INF.

The expected time complexity is \(O((n+m)\log n)\) on average leveraging a priority queue.

inputFormat

The input is provided on standard input (stdin) and has the following format:

• The first line contains three space-separated integers: \(n\) (number of nodes), \(m\) (number of edges), and \(s\) (the starting node).
• Each of the next \(m\) lines contains three space-separated integers \(u\), \(v\), and \(w\) representing an edge from node \(u\) to node \(v\) with weight \(w\).

Note that the vertices are 1-indexed.

outputFormat

Output a single line with \(n\) space-separated values. The \(i\)th number represents the shortest distance from node \(s\) to node \(i\). For unreachable nodes, output INF (without quotes).

5 6 1
1 2 2
1 3 4
2 3 1
3 4 7
2 5 10
4 5 3

0 2 3 10 12