📘

Network Delay Time

Given n nodes and times[i] = [u, v, w] (directed edge with weight), send a signal from node k. Return the minimum time for all nodes to receive the signal. Return -1 if impossible.

Input: first line = n k, second = edges as u:v:w comma-separated.

Example:

Input:

4 2
2:1:1,2:3:1,3:4:1

Output:

Reasoning:

The input 4 2 indicates there are $n = 4$ nodes and the signal is sent from node $k = 2$ .
The edges are 2:1:1, 2:3:1, and 3:4:1, which means the signal travels from node 2 to node 1 in $1$ unit of time, from node 2 to node 3 in $1$ unit of time, and from node 3 to node 4 in $1$ unit of time.
The signal reaches node 1 in $1$ unit of time and node 3 in $1$ unit of time, then reaches node 4 in $1 + 1 = 2$ units of time, making the maximum time for all nodes to receive the signal $2$ .
Since all nodes receive the signal in $2$ units of time or less, the minimum time for all nodes to receive the signal is $2$ .

Constraints:

1 <= n <= 100
1 <= times[i][2] <= 100
1 <= k <= n

Editor

Python 3.13.1

Test Results

0/0

Run code to see test results.