이번 문제는 다익스트라 알고리즘을 통해 해결하였다. 처음에 접근할 때에는 방문할 수 없는 노드에 대한 그래프를 생성하지 않는 과정을 거치고 난 후에 다익스트라 알고리즘으로 최단 거리를 구하는 방식으로 작성하였다. 그러나 이 방식으로 작성하였을 때 시간 초과가 발생하였다. 생각해보니 이 과정은 O(n)이 발생하게 되는 과정이었다.

그래서 다익스트라 알고리즘 내부에서 다음 노드로 넘어갈 때의 조건에 방문 가능한 노드인지를 확인하는 조건까지 넣어주었고 문제를 잘 해결할 수 있었다.

• input에 sys.stdin.readline을 대입한다. (시간 줄이기 위함)
• n, m을 입력받는다.
• 방문 가능 여부 리스트 aa를 입력받는다.
• aa의 가장 뒤의 원소를 지운다.
• aa에 0을 추가한다. (마지막 1을 0으로 바꾸는 과정)
• 그래프에 해당하는 리스트 graph를 2차원 리스트로 선언한다.
• m번 반복하는 for문을 돌린다.
  -> a, b, c를 입력받는다.
  -> graph[a]에 (b, c)를 넣는다.
  -> graph[b]에 (a, c)를 넣는다.
• INF에 sys.maxsize를 넣는다.
• 각 노드까지의 거리를 저장할 리스트 dist에 INF n개를 넣는다.
• dist[0]을 0으로 갱신한다.
• 다익스트라에 사용할 큐 q를 최소힙으로 선언하고 (0, 0)을 넣는다.
• q가 존재하는 동안 반복되는 while문을 돌린다.
  -> q를 추출하여 cost, cur에 저장한다.
  -> 만약 cost가 dist[cur]보다 클 경우, 다음 반복으로 넘어간다.
  -> graph[cur]을 순회하는 nxt, dst에 대한 for문을 돌린다.
  --> nxt_cost에 cost+dst의 값을 저장한다.
  --> 만약 dist[nxt]가 nxt_cost보다 크고, aa[nxt]가 0일 경우,
  ---> dist[nxt]를 nxt_cost로 갱신한다.
  ---> q에 (nxt_cost, nxt)를 넣는다.
• dist[n-1]이 INF일 경우 -1을 출력한다.
• 그 외에는 dist[n-1]을 출력한다.

Code

import sys
import heapq
input=sys.stdin.readline
n, m=map(int, input().split())
aa=list(map(int, input().split()))
aa.pop()
aa.append(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))
INF=sys.maxsize
dist=[INF for _ in range(n)]
dist[0]=0
q=[]
heapq.heappush(q, (0, 0))
while q:
    cost, cur=heapq.heappop(q)
    if cost>dist[cur]:
        continue
    for nxt, dst in graph[cur]:
        nxt_cost=cost+dst
        if dist[nxt]>nxt_cost and aa[nxt]==0:
            dist[nxt]=nxt_cost
            heapq.heappush(q, (nxt_cost, nxt))
if dist[n-1]==INF:
    print(-1)
else:
    print(dist[n-1])