Skip to content

744. Network Delay Time

Depth-First Search Breadth-First Search Graph Heap (Priority Queue) Shortest Path

Problem - Network Delay Time

Medium

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.)

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = [[] for _ in range(n)]
        priority_queue = [(0, k -1)]

        for u, v, w in times:
            graph[u - 1].append((v - 1, w))

        dists = [float('inf')] * n
        dists[k - 1] = 0

        while priority_queue:
            dist, node = heappop(priority_queue)
            if dist > dists[node]:
                continue

            for v, weight in graph[node]:
                if (cantidate := dist + weight) < dists[v]:
                    dists[v] = cantidate
                    heappush(priority_queue, (cantidate, v))

        result = max(dists)
        return result if result < inf else -1

Submission Stats:

  • Runtime: 366 ms (89.96%)
  • Memory: 19.8 MB (54.19%)