[Python/파이썬] 백준 17396번 백도어

17396번: 백도어

 

코드

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

INF = sys.maxsize

n, m = map(int, input().split())
visible = list(map(int, input().split()))
visible[n-1] = 0
graph = [[] for _ in range(n)]

for _ in range(m):
    a, b, t = map(int, input().split())
    graph[a].append((b, t))
    graph[b].append((a, t))

# Dijkstra
time = [INF]*n
time[0] = 0
q = [(0, 0)]
while q:
    t, now = heappop(q)
    if t > time[now]:   # time[now]가 t보다 더 빠른 시간으로 이미 갱신된 경우
        continue
    for nx, c in graph[now]:
        if visible[nx] == 0 and time[nx] > time[now]+c:
            time[nx] = time[now]+c
            heappush(q, (time[now]+c, nx))
print(time[n-1] if time[n-1] != INF else -1)

 

한 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘인 Dijkstra를 이용하면 된다.

 

다만 주의할 점은 보이는 분기점은 지날 수 없다는 것과 최악의 경우 n-1까지 가는 최소 시간이 int(1e10)시간까지도 나올 수 있다는 점이다. 그렇기 때문에 처음에 time 리스트의 초기값은 매우 큰 값으로 해주어야 한다.