[백준] 10282번 해킹 (파이썬)

문제링크 : https://www.acmicpc.net/problem/10282

난이도 : GOLD IV

문제해결 아이디어

• 전형적인 다익스트라 기본문제이다.

소스코드

import sys
import heapq as hq

input = sys.stdin.readline

INF = int(1e9)

for _ in range(int(input())):
    n, d, start = map(int, input().split())
    board = [[]] + [[] for _ in range(n)]
    for _ in range(d):
        a, b, s = map(int, input().split())
        board[b].append((a, s))

    distance = [INF] * (n + 1)
    q = []
    hq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, node = hq.heappop(q)
        if distance[node] < dist:
            continue

        for next, val in board[node]:
            cost = dist + val
            if distance[next] > cost:
                hq.heappush(q, (cost, next))
                distance[next] = cost

    # 반복문을 순회하면서 감염된 수, 감염된 시간을 체크한다
    cnt = 0
    _max = -1
    for i in distance:
        if i == INF:
            continue
        cnt += 1
        _max = max(_max, i)

    print(cnt, _max)