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 the n
nodes to receive the signal. If it is impossible for all the n
nodes to receive the signal, return -1
.
Example 1:
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
Example 2:
Input: times = [[1,2,1]], n = 2, k = 1
Output: 1
Example 3:
Input: times = [[1,2,1]], n = 2, k = 2
Output: -1
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. (i.e., no multiple edges.)
SOLUTION:
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
dist = [float('inf')] * n
dist[k - 1] = 0
for i in range(n - 1):
for a, b, d in times:
if dist[b - 1] > dist[a - 1] + d:
dist[b - 1] = dist[a - 1] + d
delay = max(dist)
if delay == float('inf'):
return -1
return delay
Top comments (0)