# BOJ - 13168 - 내일로 여행

Updated:

``````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))]

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

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

Categories:

Updated: