leetCode - Network Delay Time

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        
        graph = collections.defaultdict(list)
        for x, y, w in times:
            graph[x].append((y, w))
        
        dist = {}
        Q = [(0, k)]
        while Q:
            time, node = heapq.heappop(Q)
            if node not in dist:
                dist[node] = time
                for v, w in graph[node]:
                    alt = time + w
                    heapq.heappush(Q, (alt, v))
        
        max = 0
        for i in range(n):
            if i + 1 not in dist:
                return -1
            if dist[i + 1] > max:
                max = dist[i + 1]
        return max

우선순위 큐를 이용한 다익스트라 알고리즘 구현이다.