Given a weighted directed graph with non-negative edge weights and a source node, return the shortest distance from the source to every node in the graph.
Input
graph: an adjacency list wheregraph[u]is an array of[v, weight]pairs meaning there is a directed edge fromutovwith the given weight.source: the index of the starting node.
Output
Return an array
dist of length n where dist[i] is the shortest total weight from source to node i. If a node is unreachable, its entry should be Infinity.Example
Input:
graph = [
[[1, 4], [2, 1]],
[[3, 1]],
[[1, 2], [3, 5]],
[]
]
source = 0
Output: [0, 3, 1, 4]
Explanation: From 0, the cheapest path to 1 goes 0→2→1 (cost 1+2=3), to 2 directly (cost 1), to 3 via 0→2→1→3 (cost 1+2+1=4).