10217_KCM Travel

https://www.acmicpc.net/problem/10217

10217번: KCM Travel

 

 

되게 어려운 문제였다..

 

처음에는 시간을 최소로 하는 알고리즘을 찾으며 비용의 제약을 두는방식으로 하면 될것 같았으나, 생각을 해보니 당장은 시간도 비용도 손해같지만 결국 초반에 돌아가야하는 경우가 생겼다.

 

 

1
6 149 8
1 2 60 20
2 3 30 70
1 3 100 80
1 3 20 180
3 4 20 100
3 5 150 20
5 6 50 40
4 6 30 50

 

 

위와같은 경우이다.

간단히 그리면 위와 같은데, 3번까지 이동할때  20원에 180시간이 걸리는건 매우 비효율적으로 보이지만 결국에는 최소거리이다.. 그렇다면 이러한 값들을 어디다가 기록해야 하지않을까? 란 생각이 들었다.

 

어딘가에 기록하면서 알고리즘을 진행하려면 dp개념이 필요하다.

 

하지만 dp를 어떻게 구성하고 뭘 채워야하는지 감이 잘오지않아 인터넷을 살짝 참고했다..

 

 

 

문제를 풀때 한가지 간과하고 있던게 있었는데, 문제 해결시간이 10초로 되게 넉넉하게 주었던 것! 알고보니 dp에 각 비용별 최단거리를 일일히 기록하는것이 해답이었다.

 

즉, 100원이 최대 비용이라면, 1원부터 100원까지일 경우의 최단거리를 다 구해놓는 것이다.

 

1원으로 갈수있는 거리, 2원으로 갈 수 있는거리... 채워나가는것이 핵심

 

단 이 dp배열을 채울때 주의할 점이 하나있다.

 

5원으로 갈수있는 도시가 있다면, 그도시를 6원으로 딱맞춰 갈 수 없다고 하더라도 6원으로 갈 수 있는 도시안에는 포함되기에 이를 다같이 바꾸어주어야 한다.

 

어느정도 규칙을 이해했다면 코드를 보면 이해하기는 편할 것이다.

 

import sys
from collections import deque
input = sys.stdin.readline
INF = int(1e9)

t = int(input())
for _ in range(t):
    n,m,k = map(int,input().split())
    graph = [ [] for _ in range(n+1)]

    for _ in range(k):
        u,v,c,d = map(int,input().split())
        graph[u].append((v,c,d))

    dist = [ [INF] * (m+1) for __ in range(n+1)]
    dist[1][0] = 0
    q = deque([(0,0,1)])

    while q:
        time,cost,node = q.popleft()

        if dist[node][cost] < time:
            continue

        for city,c,t in graph[node]:
            tmp_c = cost + c
            tmp_t = time + t

            if tmp_c <=m and tmp_t < dist[city][tmp_c]:
                for i in range(tmp_c,m+1):
                    if tmp_t < dist[city][i]:
                        dist[city][i] = tmp_t
                    else:
                        break
                q.append((tmp_t,tmp_c,city))

    print( dist[n][m] if dist[n][m] != INF else 'Poor KCM')

 

자력으로 끝까진 풀지 못했지만 재밌었던 문제였다.