[백준 13907번] 세금 (Python3)

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. 세금을 올릴 때마다 (통행료 + 간선의 개수*세금) 의 최솟값을 출력한다.

 

쉽지 않은 문제였다. 다 익스트라 응용문제는 항상 어려운 것 같다.

 

 

오늘의 교훈) 다 익스트라 응용문제를 많이 풀어보자