LC 0743 [M] Network Delay Time - ALawliet/algorithms GitHub Wiki

Djikstra's is similar to Prim's MST which is just BFS + priority queue

O(E * logv)

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        edges = defaultdict(list)
        
        for u, v, w in times:
            edges[u].append((v,w))
            
        minHeap = [(0, k)]
        visit = set()
        t = 0
        
        while minHeap:
            # get next
            w1, n1 = heappop(minHeap) # w1 is the time to takes to reach this node
            if n1 in visit:
                continue
            # go next
            visit.add(n1)
            t = max(t, w1)
            # go neighbors
            for n2, w2 in edges[n1]:
                if n2 not in visit:
                    heappush(minHeap, (w2 + w1, n2)) # w2 is just that edge so add w1 for total path len
                    
        return t if len(visit) == n else -1