문제

• 골드5
  https://acmicpc.net/problem/17396

풀이

• 다익스트라

시작점과 도착점이 하나로 정해져 있고 최단 거리를 구하는 문제여서 다익스트라 문제라고 쉽게 생각해낼 수 있었다. 좀 특이한 점은 방문할 수 없는 노드가 존재한다는 것인데, 다익스트라 함수에서 다음 노드를 갱신하고 pq에 담을지 확인하는 부분에서 다음 노드가 방문할 수 있는지 확인해주는 조건을 추가하면 해결할 수 있다.
문제에서 마지막 도착점을 무조건 1로 세팅해두지만 방문할 수 있는 점이고 방문해야 답이 제대로 나오기 때문에 마지막 도착점을 0으로 바꿔주었다.

코드

import sys
import heapq

# 다익스트라

input = sys.stdin.readline
N,M = map(int, input().split())

arr = list(map(int, input().strip().split()))
arr[-1] = 0 # 편의상 마지막 분기점을 0으로 바꿔준다.

INF = sys.maxsize

# 양방향 그래프 연결
connect = [[] for _ in range(N)]
for i in range(M):
    a, b, t = map(int, input().split())
    connect[a].append((t, b))
    connect[b].append((t, a))


# 다익스트라(출발지와 도착지가 하나씩으로 정해져있고 최단 거리를 찾는 문제라 다익스트라 라고 생각했음)
def dijkstra(start, end):
    dis_list = [INF for _ in range(N)]
    dis_list[start] = 0

    pq = []
    heapq.heappush(pq, (0, start))

    while pq:
        dis, node = heapq.heappop(pq)
        #갱신된 게 이미 더 작을 경우에는 넘어감
        if dis > dis_list[node]:
            continue

        # 다음 노드의 거리가 새롭게 생긴 다음 노드의 거리보다 크고 /// 다음 노드가 방문할 수 있는 노드인 경우에 거리 업데이트하고 pq에 넣어줌
        for next_cost, next_node in connect[node]:
            if dis_list[next_node] > dis_list[node]+next_cost and not arr[next_node]:
                dis_list[next_node] = dis_list[node]+next_cost
                heapq.heappush(pq, (dis_list[next_node], next_node))

    #print(dis_list)
    return dis_list[end]

num = dijkstra(0, N-1)
if num==INF:
    print(-1)
else:
    print(num)