백준 10217번: KCM Travel (Python, PyPy3)

접근

굉장히 어려웠고 혼자 해결하지 못하여 다른 분들의 풀이를 많이 참고하여 진행하게 되었다. 최대 비용이 정해져 있는 점에 착안하여 냅색 알고리즘을 약간 혼합하여 풀었다.

Python으로는 시간초과하여 PyPy3으로 통과하였다.

코드

import sys

INF = float('inf')
for _ in range(int(sys.stdin.readline())):
    n, m, k = map(int, sys.stdin.readline().split())
    ticket = [[] for _ in range(n + 1)]
    for __ in range(k):
        u, v, c, d = map(int, sys.stdin.readline().split())
        ticket[u].append([v, c, d])

    dp = [[INF for __ in range(m + 1)] for ___ in range(n + 1)]
    dp[1][0] = 0

    for c in range(m + 1):
        for d in range(1, n + 1):
            if dp[d][c] == INF:
                continue
            t = dp[d][c]
            for dv, dc, dd in ticket[d]:
                if dc + c > m:
                    continue
                dp[dv][dc + c] = min(dp[dv][dc + c], t + dd)

    result = min(dp[n])

    if result == INF:
        print('Poor KCM')
    else:
        print(result)

더 생각해 볼 것?

아직 공부가 부족하여 제대로 된 설명을 할 수가 없다. 필히 다시 공부해야 할 문제이다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!