Description
Directed edges [source, target, duration] describe travel times between nodes labeled 1..n. A signal begins at k. Return when every node has received it, or -1 if any node is unreachable. Durations are nonnegative.
Solution
def network_delay_time(times, n, k):
edges = [[] for _ in range(n)]
for source, target, duration in times:
edges[source - 1].append((target - 1, duration))
distance = [float("inf")] * n
used = [False] * n
distance[k - 1] = 0
for _ in range(n):
node = min((i for i in range(n) if not used[i]), key=lambda i: distance[i])
if distance[node] == float("inf"):
return -1
used[node] = True
for target, duration in edges[node]:
distance[target] = min(distance[target], distance[node] + duration)
return max(distance)Examples
Example 1
- Input
[[[2,1,1],[2,3,1],[3,4,1]],4,2]- Output
2
Node 4 receives the signal after two units.
Example 2
- Input
[[[1,2,1]],2,1]- Output
1
The only other node is one edge away.
Example 3
- Input
[[[1,2,1]],2,2]- Output
-1
Node 2 cannot send a signal back to node 1.
Approach
Run Dijkstra's algorithm with an array of tentative distances. Repeatedly scan for the unused node with smallest distance, finalize it, and relax its outgoing edges. Return the largest final distance if all are reachable.
Time & space
O(V^2 + E) time and O(V + E) auxiliary space, where V = n and E is edge count.