Standard Bar Graphs · Shortest Path Problems O(E log V) · O(V + E)
A cluster controller pushes a config update from one master node across one-way latency links. The rollout finishes when the slowest node has received the update via its cheapest route, so ops needs the maximum, over all nodes, of the shortest latency from the master — or proof that some node can never be reached.
Input: An integer n (nodes 1..n), a list times where [u, v, w] is a one-way link u -> v costing w, and the originating node k.
Output: Return the minimum time for every node to receive the signal — the largest shortest-path distance from k — or -1 if some node is unreachable.
1 <= n <= 1001 <= times.length <= 60001 <= w <= 1001 <= k <= nInput: {"n":4,"k":2,"times":[[2,1,1],[2,3,1],[3,4,1]]}
Output: 2
Nodes 1 and 3 get it in 1 tick; the farthest, node 4, waits 2.
Input: {"n":3,"k":1,"times":[[1,2,1]]}
Output: -1
Node 3 never hears anything — the rollout fails.