Network Delay Time

Medium

Description

A network has n nodes, numbered from 1 to n. The list times holds one-way links [u, v, w]: a signal sent from node u reaches node v after w units of time.

A signal starts at node k at time 0. Return the time at which the last node receives it. If some node never receives the signal, return -1.

Examples

Example 1:

Input: times = [[1,2,3],[1,3,1],[3,2,1],[2,4,2]], n = 4, k = 1
Output: 4
Explanation: Node 3 gets the signal at time 1. Node 2 gets it at time 2 (through node 3). Node 4 gets it at time 4. The last node is reached at time 4.

Example 2:

Input: times = [[1,2,5]], n = 3, k = 1
Output: -1
Explanation: There is no link to node 3, so it never gets the signal.

Example 3:

Input: times = [[2,1,4],[2,3,6]], n = 3, k = 2
Output: 6
Explanation: Node 1 gets the signal at time 4 and node 3 at time 6. The answer is 6.

Depth-First Search
Breadth-First Search
Graph
Heap (Priority Queue)
Shortest Path

Constraints

1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= ui, vi <= n
ui != vi
0 <= wi <= 100
No two links have the same pair (ui, vi).

Examples

3 shown

Example 1

Input

[[1,2,3],[1,3,1],[3,2,1],[2,4,2]]
4
1

Output

Example 2

Input

[[1,2,5]]
3
1

Output

-1

Example 3

Input

[[2,1,4],[2,3,6]]
3
2

Output

Opening the editor...