[파이썬] 743. Network Delay Time - 리트코드

문제

K부터 출발해 모든 노드가 신호를 받을 수 있는 시간을 계산하라. 불가능할 경우 -1을 리턴한다. times배열안에 값들은 각각 출발지, 도착지, 소요시간 순으로 구성되며, 전체 노드의 개수는 N으로 입력받는다.

예제 입력

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2

예제 출력

Output: 2

작성한 코드

import heapq
from typing import List


def networkDelayTime(times: List[List[int]], n: int, k: int) -> int:
    INF = int(1e9)

    graph = [[] for _ in range(n + 1)]

    for i in times:
        a, b, c = map(int, i)
        graph[a].append((b, c))

    def dijkstra_pq(graph, start):
        N = len(graph)
        dist = [INF] * N

        q = []
        heapq.heappush(q, (0, start))
        dist[start] = 0

        while q:
            acc, cur = heapq.heappop(q)

            if dist[cur] < acc:
                continue

            for adj, d in graph[cur]:
                cost = acc + d
                if cost < dist[adj]:
                    dist[adj] = cost
                    heapq.heappush(q, (cost, adj))

        return dist


    dist = dijkstra_pq(graph, k)
    m = 0
    for d in range(1, len(dist)):
        if INF <= dist[d]:
            return -1
        m = max(m, dist[d])
    return m

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

Network Delay Time - LeetCode