Network Delay Time
Intuition
Solution
class Solution:
def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
"""Dijkstra"""
times = [[u - 1, v - 1, w] for u, v, w in times]
K -= 1
edges = [[] for _ in range(N)]
for u, v, w in times:
edges[u].append([v, w])
values = [None] * N
heap = []
heapq.heappush(heap, [0, K])
values[K] = 0
visited = [False] * N
while heap:
value, cur = heapq.heappop(heap)
if visited[cur]:
continue
visited[cur] = True
for child, length in edges[cur]:
if values[child] is None or length + values[cur] < values[child]:
values[child] = length + values[cur]
heapq.heappush(heap, [values[child], child])
if None in values:
return -1
return max(values)