import sys
input = sys.stdin.readline
from heapq import *
N,M,K = map(int,input().split())
start,end = map(int,input().split())
graph = [[] for i in range(N+1)]
for _ in range(M):
a,b,w = map(int,input().split())
graph[a].append((b,w))
graph[b].append((a,w))
DP,CNT = [1e9]*(N+1),[0]*(N+1)
hq = [(0,0,start)]
while hq:
w,cnt,now = heappop(hq)
if DP[now] <= w:
continue
DP[now] = w
CNT[now] = cnt
for next,w1 in graph[now]:
heappush(hq,(w+w1,cnt+1,next))
c = max(CNT)
DP = [[1e9]*(N+1) for i in range(c+1)]
hq = [(0,0,start)]
while hq:
w,cnt,now = heappop(hq)
if cnt>CNT[now] or DP[cnt][now]<=w:
continue
DP[cnt][now] = w
for next,w1 in graph[now]:
heappush(hq,(w+w1,cnt+1,next))
data = [int(input()) for i in range(K)]
tax = [0]
for i in range(K):
tax.append(tax[-1]+data[i])
for k in range(K+1):
MIN = 1e9
for cnt in range(c+1):
MIN = min(MIN,DP[cnt][end]+tax[k]*cnt)
print(MIN)
다 익스트라 응용문제.
아이디어를 떠올리기 쉽지 않았다.
일단 다 익스트라를 K번 하는 방법은 절대 안될 것은 알고 있었다. 그래서 다 익스트라를 하면서 비용+간선의 개수를 저장해야한다 까지는 떠올렸는데, 그걸 어떻게 구현하느냐가 문제였다.
일단 처음에는 DP를 2차원으로 만들어 DP[간선의개수][비용] 으로 일반적인 다 익스트라와 똑같이 풀어보려고 했는데, 이렇게 되자 무한루프가 일어나면서 메모리초과가 발생하였다. 그래서 개수의 상한선을 정할 필요가 있었는데, 어떻게 해결할까 고민하다가 다 익스트라를 두번 실행하는 것으로 해결하였다.
풀이를 설명하면,
1. 다 익스트라를 하면서 최소거리를 측정한다. 이때 최소거리를 위해서 지나는 간선의 개수도 저장해준다.
2. 1번에서 구한 간선의 개수를 상한선으로 두고 다 익스트라를 한번 더 한다. 이때는 현재 간선의 개수가 1에서 구한 간선의 개수보다 커지면 continue 하고 (간선의 개수가 더 많으면 세금을 더 많이 받기 때문에 필요없는 데이터이다) 각 간선의 개수일 때의 최소비용을 구한다.
3. 세금을 올릴 때마다 (통행료 + 간선의 개수*세금) 의 최솟값을 출력한다.
쉽지 않은 문제였다. 다 익스트라 응용문제는 항상 어려운 것 같다.
오늘의 교훈) 다 익스트라 응용문제를 많이 풀어보자