BOJ 17396번: 백도어

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

17396번: 백도어

평범한 다익스트라 문제에 방문하지 못하는 정점의 조건을 더한 문제이다.

중간에 현재 방문한 정점과 연결된 정점이 방문할 수 있는 정점인지를 확인하는 조건문을 추가했다.

 

import sys, heapq
N, M = map(int, input().split())
check = list(map(int, input().split()))
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])
ans = [float('INF')] * N

def solve(start):
    ans[start] = 0
    h = []
    heapq.heappush(h, [ans[start], start])
    while(h):
        now_dist, now_visit = heapq.heappop(h)
        if (ans[now_visit] < now_dist):
            continue
        for v, d in graph[now_visit]:
            if (check[v]==1 and v!=(N-1)):
                continue
            dist = now_dist + d
            if (dist < ans[v]):
                ans[v] = dist
                heapq.heappush(h, [dist, v])
                
solve(0)
if (ans[N-1]==float('INF')): print(-1)
else: print(ans[N-1])