[Python/파이썬] 백준 10282번 해킹

https://www.acmicpc.net/problem/10282

 

코드

from heapq import heappop, heappush
import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n, d, c = map(int, input().split())
    graph = [[] for _ in range(n+1)]
    for _ in range(d):
        a, b, s = map(int, input().split())
        heappush(graph[b], (s, a))
    # Dijkstra
    dist = [int(1e9)] * (n+1)
    dist[c] = 0
    hq = [(0, c)]
    while hq:
        t, now = heappop(hq)
        if dist[now] < t:
            continue
        for ns, nx in graph[now]:
            if t+ns < dist[nx]:
                dist[nx] = t+ns
                heappush(hq, (t+ns, nx))
    ans = [0, 0]
    for i in range(1, n+1):
        if dist[i] != int(1e9):
            ans[0] += 1
            if dist[i] > ans[1]:
                ans[1] = dist[i]
    print(*ans)

 

다익스트라 알고리즘을 이용하여 처음 해킹당한 컴퓨터로부터 다른 모든 컴퓨터까지 도달하는 시간을 구한다. 이때 우선순위큐를 이용하여 현재 노드(now)에서 인접한 노드들 중 가장 적은 시간이 필요한 노드부터 골라서 현재 노드(now)를 지나쳐서 인접 노드(nx)로 가는 것이 더 빠를 경우에는 dist[nx]를 t+ns로 업데이트해준다.