Proficient Level
Implement the networkDelayTimeCost method that returns the time needed for a signal to reach all nodes.
You are given a directed weighted graph as edges [from, to, time], the number of nodes, and a source node. Nodes are numbered from 1 to nodes.
Return the minimum time required for the signal to reach every node. If any node cannot be reached, return -1.
Example 1
Input
nodes (int) =
4edges (int[][]) =
[[2,1,1],[2,3,1],[3,4,1]]size (int) =
3source (int) =
2Returns (int)
2Example 2
Input
nodes (int) =
2edges (int[][]) =
[[1,2,1]]size (int) =
1source (int) =
1Returns (int)
1Example 3
Input
nodes (int) =
2edges (int[][]) =
[[1,2,1]]size (int) =
1source (int) =
2Returns (int)
-1This is a shortest path problem from one source to all nodes.
Build an adjacency list and run Dijkstra's algorithm using a min heap. Each time the nearest unprocessed node is selected, relax its outgoing edges. After processing, the answer is the largest shortest distance among all nodes.
If any node still has infinite distance, not every node can receive the signal.
Pseudocode:
function networkDelayTimeCost(nodes, edges, size, source):
build graph from edges
distance = array filled with infinity
distance[source] = 0
heap = min heap with [0, source]
while heap is not empty:
[time, node] = remove minimum
if time > distance[node]:
continue
for each [next, weight] in graph[node]:
if time + weight < distance[next]:
distance[next] = time + weight
push [distance[next], next] into heap
answer = maximum distance from 1 to nodes
if answer is infinity:
return -1
return answerReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run