Leetcode 744 Solution

This article provides solution to leetcode question 744 (network-delay-time)
Categories:
Tags:
Access this page by simply typing in "lcs 744" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/network-delay-time

Solution

class Solution(object):
    def networkDelayTime(self, times, N, K):
        """
        :type times: List[List[int]]
        :type N: int
        :type K: int
        :rtype: int
        """
        edges = collections.defaultdict(list)
        for u, v, w in times:
            edges[u].append((v, w))

        heap = [(0, K)]
        dist = {}

        while heap:
            d, i = heapq.heappop(heap)
            if i in dist:
                continue
            dist[i] = d
            for j, w in edges[i]:
                if j not in dist:
                    heapq.heappush(heap, (w + d, j))

        return max(dist.values()) if len(dist) == N else -1