[백준 10217번] KCM Travel (Python3)

import sys
input = sys.stdin.readline
from heapq import *

for _ in range(int(input())):
  N,M,K = map(int,input().split())
  
  graph = [[] for i in range(N)]
  for _ in range(K):
    a,b,c,d = map(int,input().split())
    graph[a-1].append((b-1,c,d))
  
  hq = [(0,0,0)]; distance = [1e9]*N; DP = [1e9]*N
  while hq:
    c,now,d = heappop(hq)
    if DP[now] < c:
      continue
    for next,c1,d1 in graph[now]:
      if DP[next] > c+c1:
        DP[next] = c+c1; distance[next] = d+d1
        heappush(hq,(c+c1,next,d+d1))
  
  hq = [(0,0,0)]; DP = [[1e9]*(M+1) for i in range(N)]
  while hq:
    d,now,c = heappop(hq)
    if DP[now][c] < d:
      continue
    for next,c1,d1 in graph[now]:
      if c+c1<=M and DP[next][c+c1] > d+d1 <= distance[next]:
        DP[next][c+c1] = d+d1
        heappush(hq,(d+d1,next,c+c1))
    
  print(min(DP[-1]) if min(DP[-1])!=1e9 else "Poor KCM")

다 익스트라 응용문제

2차원 배열을 이용해서 해결 가능하다.

 

내가 푼 아이디어를 설명하면,

1. 비용에 대한 다 익스트라를 실행하여 최소비용으로 이동할 때의 비용을 구하고, 이때의 거리를 구한다.

2. 1에서 구한 거리를 상한선으로 잡고, 노드*비용의 2차원 DP에 대해서 다 익스트라를 실행한다.

3. 최솟값을 출력한다.

 

1에서 상한을 정한 이유는, 그냥 처음부터 2차원 다 익스트라를 실행했을 때에는 시간초과가 발생했기 때문이다. 최소비용으로 이동한 거리보다 더 큰 거리인 경우는 고려할 가치가 없기 때문에 커팅해줄 수 있다.

 

이 풀이로 똑같이 풀었을 때 메모리 초과가 발생했었는데, 달빛 여우 [백준 16118번] 달빛 여우 (Python3) (tistory.com) 문제 덕분에 내 다 익스트라 구현방식에 문제가 있음을 알게되었고, 이를 수정하자 정답처리가 되었다.

 

 

더 좋은 풀이도 알게 되었는데, 2차원 DP에 대해서 거리를 갱신할 때, DP[next][c]만 갱신하는 것이 아니고, c~M+1까지 현재 비용보다 큰 모든 비용에 대해서 갱신해줄 수 있는 것을 활용할 수 있다.

 

코드는 다음과 같다.

import sys
input = sys.stdin.readline
from heapq import *

for _ in range(int(input())):
  N,M,K = map(int,input().split())
  
  graph = [[] for i in range(N)]
  for _ in range(K):
    a,b,c,d = map(int,input().split())
    graph[a-1].append((b-1,c,d))
  
  DP = [[1e9]*(M+1) for i in range(N)]
  hq = [(0,0,0)]
  while hq:
    d,now,c = heappop(hq)
    if DP[now][c]<d:
      continue
    for next,c1,d1 in graph[now]:
      if c+c1<=M and DP[next][c+c1]>d+d1:
        for c2 in range(c+c1,M+1):
          if DP[next][c2] > d+d1:
            DP[next][c2] = d+d1
          else:
            break
        heappush(hq,(d+d1,next,c+c1))
  print(min(DP[-1]) if min(DP[-1])!=1e9 else "Poor KCM")

 

해당 코드로 제출하자 위 코드보다 시간이 5배가량 줄어든 결과를 보여주었다.

 

 

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