Network Delay Time

Statement

A network of n nodes labeled $1$ to $n$ is provided along with a list of travel times for directed edges represented as $times[i]=(x_i​, \space y_i, \space t_i​)$, where $x_i$​ is the source node, $y_i$​ is the target node, and $t_i$​ is the delay time from the source node to the target node.

Considering we have a starting node, k, we have to determine the minimum time required for all the remaining $n - 1$ nodes to receive the signal. Return $-1$ if it’s not possible for all $n - 1$ nodes to receive the signal.

Constraints:

• $1 \leq$ k $\leq$ n $\leq$ $100$
• $1 \leq$ times.length $\leq$ $6000$
• times[i].length $== 3$
• $1 \leq x, y \leq$ n
• $x$ $!=$ $y$
• $0 \leq t \leq 100$
• Unique pairs of $(x, y)$, which means that there should be no multiple edges

Examples

Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Try it yourself

Implement your solution in the following coding playground.