All problems

Network Delay Time

Medium · shortest path

A network has n computers, labelled 1 to n. The one-way links are given as a list times of triples [u, v, w]: a message sent by computer u over this link arrives at computer v exactly w minutes later.

At minute 0, computer k creates a signal. Every computer that receives the signal passes it on immediately over all of its outgoing links, and a computer keeps the earliest copy it receives. Return the number of minutes until every computer has received the signal. If at least one computer never receives it, return -1.

Several links may join the same pair of computers, and a link may start and end at the same computer. If n is 1, the answer is 0.

Examples

Example 1

Input: times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]], n = 4, k = 2

Output: 2

Computers 1 and 3 hear the signal at minute 1, and computer 4 hears it from computer 3 at minute 2.

Example 2

Input: times = [[1, 2, 4]], n = 2, k = 1

Output: 4

The only link takes 4 minutes, so computer 2 is the last to hear it.

Example 3

Input: times = [[1, 2, 4]], n = 2, k = 2

Output: -1

Computer 2 has no outgoing links, so computer 1 never receives the signal.

Constraints