1026. Dijkstra's Shortest Path Algorithm

Given a directed weighted graph with n nodes and edges [u, v, w] (w >= 0), return an array of the shortest-path distances from a source node src to every node (use -1 for unreachable nodes). The input is JSON {n, edges, src}.

Input: JSON {n, edges, src} with edges [u, v, w].

Output: Array — shortest distance to each node, or -1.

Examples

Input: {"n":5,"edges":[[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5]],"src":0}
Output: [0,3,1,4,-1]
Explanation: Shortest distances from node 0.

Input: {"n":1,"edges":[],"src":0}
Output: [0]
Explanation: Only the source.

Input: {"n":3,"edges":[[0,1,2]],"src":0}
Output: [0,2,-1]
Explanation: Node 2 unreachable.

Constraints

• 1<=n<=10^5
• 0<=w<=10^4
• directed

Asked by