[백준 🥇3] 13168번 내일로 여행 (Python/파이썬)

1️⃣ 문제

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

2️⃣ 코드

플로이드 문제는 티어에 비해 쉬운 느낌ㅎㅎ
이 문제도 첨에 입력 보고 경악했지만 풀고보니 쉬운 문제였다

import sys

INF = sys.maxsize

n, r = map(int, sys.stdin.readline().split())
city = {}
temp = list(sys.stdin.readline().split())
for i in range(n):
    city[temp[i]] = i   # 딕셔너리를 이용해 'city[도시이름] = 인덱스'로 정리함
    
m = int(sys.stdin.readline())
temp = list(sys.stdin.readline().split())
travel = []
for i in range(m):
    travel.append(city[temp[i]])   # 여행할 도시 인덱스 리스트로 저장함

k = int(input())
dist = [[INF] * n for _ in range(n)]    # 내일로를 사지 않았을 때 최소 비용
tomo = [[INF] * n for _ in range(n)]    # 내일로를 샀을 때 최소 비용

for _ in range(k):
    t, ss, es, c = input().split()

    s, e = city[ss], city[es]
    # 내일로를 사지 않았을 때 비용 저장 
    if dist[s][e] > int(c):
        dist[s][e] = int(c)
        dist[e][s] = int(c)

    # 내일로를 샀을 때 비용 저장
    if t == 'Mugunghwa' or t == 'ITX-Saemaeul' or t == 'ITX-Cheongchun':
        tomo[s][e] = 0
        tomo[e][s] = 0
    elif t == 'S-Train' or t == 'V-Train':
        if tomo[s][e] > int(c) / 2:
            tomo[s][e] = int(c) / 2
            tomo[e][s] = int(c) / 2
    else:
        if tomo[s][e] > int(c):
            tomo[s][e] = int(c)
            tomo[e][s] = int(c)

# 플로이드 알고리즘으로 최소 비용 구하기 
for l in range(n):
    for i in range(n):
        for j in range(n):
            if dist[i][j] > dist[i][l] + dist[l][j]:
                dist[i][j] = dist[i][l] + dist[l][j]
                dist[j][i] = dist[j][l] + dist[l][i]

            if tomo[i][j] > tomo[i][l] + tomo[l][j]:
                tomo[i][j] = tomo[i][l] + tomo[l][j]
                tomo[j][i] = tomo[j][l] + tomo[l][i]

# m개의 도시를 차례대로 이동하는데 드는 비용 계산
yes, no = r, 0
for i in range(m-1):
    s, e = travel[i], travel[i+1]
    yes += tomo[s][e]
    no += dist[s][e]

if yes >= no:
    print('No')
else:
    print('Yes')

3️⃣ 풀이

헷갈렸던 부분은 A 도시에서 B 도시로 갈 때 드는 비용과 B 도시에서 A 도시로 올 때 드는 비용이 동일하다는 것
그리고 50% 비용을 계산할 때 정수 나누기로 해주면 틀린다
100%에서 틀려서 질문 게시판 보고 알았음