leetcode 743(medium)

문제

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

내 풀이

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = collections.defaultdict(list)
        for start,end,weight in times:
            graph[start].append((weight,end))
            
        d = {i:float('inf') for i in range(1,n+1)}
        d[k] = 0
        
        q = [(0,k)]
        while(q):
            cur_dist, cur_node = heapq.heappop(q)
            if cur_dist > d[cur_node]: continue
            
            for weight, neighbor in graph[cur_node]:
                print((weight,neighbor))
                if cur_dist + weight < d[neighbor]:
                    d[neighbor] = cur_dist + weight
                    heapq.heappush(q,(d[neighbor], neighbor))
                
        if float('inf') in d.values():
            return -1
        
        else :
            return max(d.values())
                     
        

전형적인 다익스트라 문제였다