[백준 13308번] 주유소 (Python3)

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) 문제를 풀면서 내 다 익스트라 구현방식이 잘못되었다는 것을 알게되었었는데, 이 문제도 마찬가지였다. 다 익스트라를 잘못 구현해서 계속 시간초과가 발생하였는데, 이를 수정하자 맞게되었다.

 

 

오늘의 교훈) 다 익스트라를 정확하게 구현하자