import sys
input = sys.stdin.readline
from heapq import *
def dij():
hq = [(0,cost[0],0)]; DP = [[1e12]*N for i in range(cost[0]+1)]
while hq:
w,c,now = heappop(hq)
if now==N-1:
return w
if DP[c][now] < w:
continue
for next,w1 in graph[now]:
c1 = min(c,cost[next])
if DP[c1][next] > w+w1*c:
DP[c1][next] = w+w1*c
heappush(hq,(w+w1*c,c1,next))
N,M = map(int,input().split())
cost = [*map(int,input().split())]
graph = [[] for i in range(N)]
for _ in range(M):
a,b,w = map(int,input().split())
graph[a-1].append((b-1,w))
graph[b-1].append((a-1,w))
print(dij())
다 익스트라 응용문제이다.
풀이는 쉽게 떠올랐는데 잘못된 다 익스트라 코드로 인해서 시간초과가 발생했던 문제
풀이부터 설명하면,
1. DP 배열을 2차원으로 만든다. DP[c][now]는 현재까지의 주유소 기름의 최솟값이 c일때 노드 now에서의 최솟값을 의미한다.
2. cost는 min으로 갱신하고, w는 w+c*가중치로 갱신하면서 다 익스트라를 실행한다.
3. now에 도착하면 w를 return한다.
이전에 달빛 여우 [백준 16118번] 달빛 여우 (Python3) (tistory.com) 문제를 풀면서 내 다 익스트라 구현방식이 잘못되었다는 것을 알게되었었는데, 이 문제도 마찬가지였다. 다 익스트라를 잘못 구현해서 계속 시간초과가 발생하였는데, 이를 수정하자 맞게되었다.
오늘의 교훈) 다 익스트라를 정확하게 구현하자