Date and Time: Sep 25, 2024, 22:20 (EST)
Link: https://leetcode.com/problems/network-delay-time/
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] = (u_i, v_i, w_i)
, where u_i
is the source node, v_i
is the target node, and w_i
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
-
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.)
-
Run Dijkstra's Algorithm to find the shortest path from
k
ton
. We useminHeap
to implement this. -
Store all src's target into
edges
with their weight, we can use them later. -
Store current node's neighbors and their weights into
minHeap
. And for each time, we update theres = max(res, weight)
, and then we append this node's neighbors and weights intominHeap
. -
Finally, we return
res
iflen(visited) == n
, that means we traverse all the nodes, otherwise, we should return-1
.
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
# Dijkstra's algorithm, maintain a minHeap [weight, node]
# From k to all n nodes
edges = collections.defaultdict(list)
for u, v, w in times:
edges[u].append((w, v))
minHeap, visited = [(0, k)], set()
res = 0
while minHeap:
w1, n1 = heapq.heappop(minHeap)
if n1 not in visited:
visited.add(n1)
res = max(res, w1)
# Append n1's neighbors into minHeap
for w2, n2 in edges[n1]:
if n2 not in visited:
heapq.heappush(minHeap, (w1+w2, n2))
return res if len(visited) == n else -1
Time Complexity: E
is total edges, V
is total vertices. Because when we explore a new edge, we need to push a new node in minHeap, which takes
Space Complexity: