Description
You are given a network of n nodes labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source, v is the target, and w is the time. Find the minimum time it takes for all nodes to receive the signal from node k. Return -1 if impossible.
Examples
Input:
times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2Output:
2Explanation:
From node 2: reach 1 and 3 in 1 unit, reach 4 via 3 in 2 units.
Input:
times = [[1,2,1]], n = 2, k = 2Output:
-1Explanation:
Node 2 cannot reach node 1.
Input:
times = [[1,2,2],[1,3,4],[2,3,1],[2,4,3],[3,4,2]], n = 4, k = 1Output:
5Explanation:
From node 1: reach node 2 in 2 units, reach node 3 via node 2 in 3 units (1→2→3), and reach node 4 via node 2 in 5 units (1→2→4). All nodes are reachable, and the maximum time is 5.
Constraints
- •
1 ≤ k ≤ n ≤ 100 - •
1 ≤ times.length ≤ 6000