(Python) 백준 10282 - 해킹

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

10282번: 해킹

 

아이디어

- 가중치가 있는 단방향 그래프에서의 최단 경로 문제로, 다익스트라 알고리즘을 사용한다

- 방문 시간을 업데이트할 때, 기존 시간이 초기값일 시 방문 노드의 개수에 1을 추가해서 구한다

- 방문 시간을 보관한 배열에서 초기값을 제외한 값 중 가장 큰 값이 걸린 시간이다

 

코드

from heapq import *
import sys
input=sys.stdin.readline
f=float('inf')
for _ in range(int(input())):
    n,d,c=map(int,input().split())
    g=[[] for _ in range(n+1)]
    v=[f]*(n+1) # 방문 시간을 매우 큰 값으로 초기화
    for _ in range(d):
        a,b,s=map(int,input().split())
        g[b]+=[(s,a)]
    q=[(0,c)]
    v[c]=0
    n=1 # 방문 횟수
    while q:
        w,c=heappop(q) 
        for (a,x) in g[c]:
            t=w+a
            if t<v[x]:
                if v[x]==f: n+=1 # 기존의 방문 시간이 초기값일 시 방문 횟수 추가
                heappush(q,(t,x))
                v[x]=t
    print(*(n,max([i for i in v if i!=f])))