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)