BOJ - 13168 - 내일로 여행

import sys
def solution():
    _discount = {"Mugunghwa" : 0, "ITX-Saemaeul" : 0, "ITX-Cheongchun" : 0, "S-Train" : 0.5 , "V-Train" : 0.5}
    _city = {}
    _INF = 1e6

    N, TICKET = map(int, sys.stdin.readline().split())
    CITY = list(map(str, sys.stdin.readline().split()))

    weight = 0
    for index, city in enumerate(CITY):
        if city in _city: 
            continue
        else: 
            _city[city] = weight
            weight += 1

    travel = [[[_INF] * 2 for _ in range(len(_city))] for _ in range(len(_city))]

    M = int(sys.stdin.readline())
    DESTINATION = list(map(str, sys.stdin.readline().split()))

    K = int(sys.stdin.readline())
    for i in range(K):
        Type, S, E, Cost = map(str, sys.stdin.readline().split())
        Cost = int(Cost)
        start = _city[S]
        end = _city[E]
        if Type in _discount:
            travel[start][end][0] = min(Cost * _discount[Type], travel[start][end][0])
            travel[end][start][0] = min(Cost * _discount[Type], travel[end][start][0])
        else:
            travel[start][end][0] = min(Cost, travel[start][end][0])
            travel[end][start][0] = min(Cost, travel[end][start][0])
        travel[start][end][1] = min(Cost, travel[start][end][1])
        travel[end][start][1] = min(Cost, travel[end][start][1])

    size = len(_city)
    for k in range(size):
        for i in range(size):
            for j in range(size):
                travel[i][j][0] = min(travel[i][j][0], travel[i][k][0] + travel[k][j][0])
                travel[i][j][1] = min(travel[i][j][1], travel[i][k][1] + travel[k][j][1])

    tomorrow_ticket = 0
    ticket = 0
    for index in range(len(DESTINATION)-1):
        start = _city[DESTINATION[index]]
        end = _city[DESTINATION[index + 1]]

        tomorrow_ticket += travel[start][end][0]
        ticket += travel[start][end][1]

    print("Yes" if tomorrow_ticket + TICKET < ticket else "No")

solution()

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