Time for a Broadcast to Reach Every Node
A control-plane node broadcasts a config change across a network of services. Each directed link has a known propagation latency. Find how long until every service has received the update, or report that some service is unreachable.
Problem
There are n services labelled 1..n. Given times where times[i] = [u, v, w] means a signal from u reaches v after w milliseconds, and a starting service k, return the minimum time for all n services to receive the signal. If not all services can be reached, return -1.
Input
A list times of [u, v, w] directed edges, an integer n, and a source k.
Output
An integer: the time for the last service to receive the signal, or -1.
Constraints
- 1 <= k <= n <= 100
- 1 <= times.length <= 6000
- 1 <= w <= 100; all (u, v) pairs are unique.
Examples
Example 1
Input
times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output
2
From 2: node 1 at t=1, node 3 at t=1, node 4 at t=2. Max is 2.
Example 2
Input
times = [[1,2,1]], n = 2, k = 2
Output
-1
Node 1 is unreachable from node 2.