Network Delay Time

Medium~25 min

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] = [ui, vi, wi], where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the minimum time it takes for all n nodes to receive the signal. If it is impossible for all n nodes to receive the signal, return -1.

Examples

Example 1
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
Explanation: From node 2, the signal reaches node 1 in 1 unit, node 3 in 1 unit, and node 4 in 2 units (via node 3). The maximum delay is 2.
Example 2
Input: times = [[1,2,1]], n = 2, k = 2
Output: -1
Explanation: The signal starts at node 2 but there is no edge from node 2, so node 1 can never be reached.
Example 3
Input: times = [[1,2,1]], n = 2, k = 1
Output: 1
Explanation: From node 1, the signal reaches node 2 in 1 unit.

Constraints

  • 1 <= k <= n <= 100
  • 1 <= times.length <= 6000
  • times[i].length == 3
  • 1 <= ui, vi <= n
  • ui != vi
  • 0 <= wi <= 100
  • All the pairs (ui, vi) are unique
  • Expected time complexity: O(V + E log V)
Code
Ctrl+EnterRun|Ctrl+⇧+EnterSubmit
Output

Run your code to see results

Use Cmd+Enter to run