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

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

17396번: 백도어

 

풀이

다익스트라 알고리즘 사용해서 풀 수 있는 문제이다.

1 , 이 문제에서 최대는 300억이 나오기에 INF 설정에 주의를 해야한다.  아래 코드에서는 INF를 1000억으로 구성했다. 코드가 더럽지 않게 리스트로 간단히 만들어서 인덱스 비교로 간선 처리를 하려했으나 집합으로 처리해보고 싶어서 처리했다. INF가 무엇인지 모르겠다면 본 블로그 알고리즘을 참고해주세요.

2, 다익스트라 적용

# 17396번 백도어
# 다익스트라 문제, 최대가 300억인 경우
import sys
import heapq
input = sys.stdin.readline
# INF 1000억
INF = int(1e11)

# 다익스트라 알고리즘 사용
def dijkstra():
    q = []
    heapq.heappush(q, (0, 0))
    distance[0] = 0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        # vertex, weight
        for v, w in graph[now]:
            cost = dist + w
            if cost < distance[v]:
                distance[v] = cost
                heapq.heappush(q, (cost, v))

n, m = map(int, input().split())

# 시야가 보여서 가짐 못하는 분기점을 set에 넣어준다.
wad = list(map(int, input().split()))
wad_set = set()
for i in range(n-1):
    if wad[i] == 1:
        wad_set.add(i)

# 다익스트라 기본 세팅
graph = [[] for i in range(n+1)]
distance = [INF] * (n+1)
for _ in range(m):
    a, b, c = map(int,input().split())
    # 앞서 만든 가지 못하는 분기점에 해당하는 vertex가 나오면 간선을 만들지않는다.
    if a not in wad_set and b not in wad_set:
        graph[a].append((b, c))
        graph[b].append((a, c))

dijkstra()
ans = distance[n-1]

if ans == INF:
    print(-1)
else:
    print(ans)

풀이결과