Medium

Network Delay Time

LAB

Given directed edges [u,v,w] with 1-indexed nodes, return how long a signal from k takes to reach all nodes, or -1.

EXAMPLES

Example 1

Input
{
  "times": [
    [
      2,
      1,
      1
    ],
    [
      2,
      3,
      1
    ],
    [
      3,
      4,
      1
    ]
  ],
  "n": 4,
  "k": 2
}

Output
2

FUNCTION SHAPE

times: intMatrixn: intk: int→int

SOLUTION NOTE

This is literally the template.

Reveal reference solution +

pythonREFERENCE

def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
    graph = [[] for _ in range(n + 1)]
    for u, v, w in times:
        graph[u].append((v, w))

    dist = [float('inf')] * (n + 1)
    dist[k] = 0

    min_heap = [(0, k)]  # (time, node)

    while min_heap:
        time, u = heapq.heappop(min_heap)
        if time > dist[u]:
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(min_heap, (dist[v], v))
    max_dist = max(dist[1:])
    return max_dist if max_dist < float('inf') else -1

TimeO((V+E)log V)

SpaceO(V+E)

Open on LeetCode ↗