[TIL_Carrotww] 7 - 22/09/06

유형석·2022년 9월 6일

JetBrain algorithm camp font python vscode

TIL

목록 보기

8/138

📝vscode Font 적용, Algorithm

🧲 알고리즘

🔗 백준 10217 KCM Travel
https://www.acmicpc.net/problem/10217

🔍다 익스트라 알고리즘인 줄 알았으나 아니여서 애좀 먹었다...

🧲 코드

import sys
import math

def solution():
    n, total_cost, tickets = map(int, sys.stdin.readline().split())
    path = [[] for _ in range(n + 1)]
    for _ in range(tickets):
        start, end, cost, time = map(int, sys.stdin.readline().split())
        path[start].append((end, cost, time))
    MAX = math.inf
    temp = [[MAX] * (total_cost + 1) for _ in range(n + 1)]
    temp[1][0] = 0

    for cost in range(total_cost + 1):
        for node in range(n + 1):
            if temp[node][cost] != MAX:
                for next_node, next_cost, next_time in path[node]:
                    if next_cost + cost <= total_cost:
                        temp[next_node][next_cost + cost] = min(temp[next_node][next_cost + cost], temp[node][cost] + next_time)
    
    result = min(temp[n])
    if result == MAX:
        print('Poor KCM')
    else:
        print(result)
        
T = int(input())
for _ in range(T):
    solution()