17396번: 백도어
첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는
www.acmicpc.net
코드
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 리스트의 초기값은 매우 큰 값으로 해주어야 한다.
'문제풀이 > 최단경로' 카테고리의 다른 글
[Python/파이썬] 백준 10282번 해킹 (0) | 2024.05.16 |
---|---|
[Python/파이썬] 백준 2660번 회장뽑기 (1) | 2024.04.16 |
[Python/파이썬] 백준 2458번 키 순서 (0) | 2024.04.12 |
[Python/파이썬] 백준 20007번 떡 돌리기 (0) | 2024.04.11 |
[Python/파이썬] 백준 18223번 민준이와 마산 그리고 건우 (0) | 2024.01.30 |