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

백준 17396 - 백도어

시간 제한 2초, 메모리 제한 512MB

# 조건

• 유섭이는 무척이나 게으르다.
• 오늘도 할 일을 모두 미뤄둔 채 열심히 롤을 하던 유섭이는 오늘까지 문제를 내야 한다는 사실을 깨달았다.
• 그러나 게임은 시작되었고 지는 걸 무척이나 싫어하는 유섭이는 어쩔 수 없이 백도어를 해 게임을 최대한 빠르게 끝내기로 결심하였다.
• 최대한 빨리 게임을 끝내고 문제를 출제해야 하기 때문에 유섭이는 최대한 빨리 넥서스가 있는 곳으로 달려가려고 한다.
• 유섭이의 챔피언은 총 N개의 분기점에 위치할 수 있다.
  • 0번째 분기점은 현재 유섭이의 챔피언이 있는 곳을, N-1 번째 분기점은 상대편 넥서스를 의미하며 나머지 1, 2, ..., N-2번째 분기점은 중간 거점들이다.
• 그러나 유섭이의 챔피언이 모든 분기점을 지나칠 수 있는 것은 아니다.
• 백도어의 핵심은 안 들키고 살금살금 가는 것이기 때문에 적 챔피언 혹은 적 와드(시야를 밝혀주는 토템), 미니언, 포탑 등 상대의 시야에 걸리는 곳은 지나칠 수 없다.
• 입력으로 각 분기점을 지나칠 수 있는지에 대한 여부와 각 분기점에서 다른 분기점으로 가는데 걸리는 시간이 주어졌을 때, 유섭이가 현재 위치에서 넥서스까지 갈 수 있는 최소 시간을 구하여라.

입력

• 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000)
• 두 번째 줄에 각 분기점이 적의 시야에 보이는지를 의미하는 N개의 정수 a0, a1, ..., aN-1가 공백으로 구분되어 주어진다.
• ai_가 0이면 _i 번째 분기점이 상대의 시야에 보이지 않는다는 뜻이며, 1이면 보인다는 뜻이다.
• 추가적으로 a0 = 0, aN-1 = 1이다.
• N-1번째 분기점은 상대 넥서스이기 때문에 어쩔 수 없이 상대의 시야에 보이게 되며, 또 유일하게 상대 시야에 보이면서 갈 수 있는 곳이다.
• 다음 M개의 줄에 걸쳐 세 정수 a, b, t가 공백으로 구분되어 주어진다. (0 ≤ a, b _< N_, a ≠ b, 1 ≤ t ≤ 100,000)
• 이는 a번째 분기점과 b번째 분기점 사이를 지나는데 t만큼의 시간이 걸리는 것을 의미한다.
• 연결은 양방향이며, 한 분기점에서 다른 분기점으로 가는 간선은 최대 1개 존재한다.

출력

• 첫 번째 줄에 유섭이의 챔피언이 상대 넥서스까지 안 들키고 가는데 걸리는 최소 시간을 출력한다.
• 만약 넥서스까지 갈 수 없으면 -1을 출력한다.

# 접근 방법

• 시작점에서 목적지까지 최단 거리를 구하는 문제이므로 다익스트라를 활용해준다.
• DIST 배열을 충분히 큰 수로 분기점 개수만큼 생성해준다.
• 이후, 양방향 그래프를 graph 리스트에 거리와 함께 넣어준다.
• 또한, 넥서스의 시야를 0으로 변경해주면서 나중에 있을 조건문을 간단하게 만들어준다.
• 출발점을 0으로 초기화한 후 dijkstra 함수를 실행해준다.
• 만약 현재 위치까지 온 거리가 기록되어 있는 거리보다 길다면 continue를 해준다.
• 또한, 넥서스라면 종료해준다.
• 이후 현재 위치에서 갈 수 있는 곳을 탐색하며, 다음 분기점까지 현재 거리 + 가야될 거리가 기록된 거리보다 짧고, 시야가 밝혀지지않았다면 heappush 해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from heapq import heappop, heappush  

def dijkstra():  
    q = []  
    heappush(q, (0, 0))  
    while q:  
        weight, node = heappop(q)  
        if node == N-1:  
            return weight  
        if dist[node] < weight:  
            continue  
        for next_node, next_weight in graph[node]:  
            val = next_weight + weight  
            if dist[next_node] > val and not arr[next_node]:  
                dist[next_node] = val  
                heappush(q, (val, next_node))  
    return -1  

N, M = map(int, input().split())  
arr = [*map(int, input().split())]  
arr[-1] = 0  
graph = [[] for _ in range(N)]  
for _ in range(M):  
    a, b, c = map(int, input().split())  
    graph[a].append((b, c))  
    graph[b].append((a, c))  

dist = [float('inf') for _ in range(N)]  
dist[0] = 0  
result = dijkstra()  
print(result)