Dijkstra
-
743. Network Delay TimeProgramming/leetcode 2021. 3. 10. 11:23
최소 비용을 구하는 문제. 음수값이 없어 다익스트라로 해결 가능하다. def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int: graph = collections.defaultdict(list) for u, v, w in times: graph[u].append((v, w)) distances = {node:float('inf') for node in range(n+1)} distances[k] = 0 q = [(0, k)] while q: weight, vertex = heapq.heappop(q) if weight < distances[vertex]: continue for new_vertex, new_weight in gr..