[백준] 17396번 - 백도어 (파이썬)

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

 

# 백도어
import heapq
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
cant_go = list(map(int, input().split()))
cant_go[-1] = 0
arr = [[]for _ in range(N)]
for _ in range(M):
    a, b, cost = map(int, input().split())
    arr[a].append((cost, b))
    arr[b].append((cost, a))
dist = [sys.maxsize] * N


def dijkstra():
    q = []
    heapq.heappush(q, (0, 0))
    dist[0] = 0
    while q:
        cost, node = heapq.heappop(q)
        if dist[node] < cost:
            continue
        for ncost, nnode in arr[node]:
            if not cant_go[nnode] and dist[nnode] > cost+ncost:
                dist[nnode] = cost+ncost
                heapq.heappush(q, (cost+ncost, nnode))


dijkstra()
print(-1) if dist[N-1] == sys.maxsize else print(dist[N-1])

 

최단거리, 다익스트라
1. 입력을 받는다.
2. N-1은 넥서스이므로 cant_go[-1]을 0으로 초기화해준다. (0은 갈 수 있는 장소)
3. 다익스트라
    - 방문 처리된 곳은 continue
    - 연결된 모든 노드들 중, 갈 수 있는 노드이고 최단거리가 업데이트가 된다면 업데이트
4. dist[N-1]이 초기화가 됐다면 출력 아니면 -1