문제
https://www.acmicpc.net/problem/13168
접근
- 문제를 처음 보고 내일로 티켓을 구입했을 때와 구입하지 않았을 때의 비용 정보를 따로 저장하고, 동일한 최단거리 알고리즘으로 비용을 계산한 후 비교해야 겠다고 생각했다.
- 경로마다 비용이 다르므로 다익스트라와 플로이드 워셜 중 하나를 이용하기로 했다.
- 문제에서 방문하려는 곳의 전체 경로가 정해져 있고 각 부분 경로마다 최단거리로 이동해서 목적지까지 드는 비용을 계산할 것이므로 플로이드-워셜을 이용했다.
풀이
- 주어지는 도시 이름을 각각의 인덱스와 매핑시키기 위해 딕셔너리를 이용했다. mapping[도시이름] = 인덱스
- 내일로 티켓을 구입하는 경우 ITX-Saemaeul, ITX-Cheongchun, Mugunghwa의 비용은 0으로, S-Train과 V-Train의 비용은 주어지는 비용의 절반으로 계산했다.
- 이때 절반으로 나누는 작업 때문에 int로 계산하지 않고 float으로 계산
- 또한 동일한 경로지만 교통수단과 비용이 다른 경우가 입력으로 들어올 수 있으므로, 값을 넣을 때 기존 값과 비교하여 더 작은 값으로 저장했다.
import sys
input = sys.stdin.readline
n, r = map(int, input().split())
cities = input().rstrip().split()
mapping = dict()
i = 0
for city in cities:
if city not in mapping:
mapping[city] = i
i += 1
n = i
m = int(input())
route = input().split()
k = int(input())
cost = [[1e9] * n for _ in range(n)]
free_pass = [[1e9] * n for _ in range(n)]
for i in range(n):
cost[i][i] = 0
free_pass[i][i] = 0
for _ in range(k):
x = input().rstrip().split()
a, b = mapping[x[1]], mapping[x[2]]
x[3] = float(x[3])
cost[a][b] = min(cost[a][b], x[3])
cost[b][a] = min(cost[b][a], x[3])
if x[0] in ["ITX-Saemaeul", "ITX-Cheongchun", "Mugunghwa"]:
free_pass[a][b] = 0
free_pass[b][a] = 0
elif x[0] in ["V-Train", "S-Train"]:
free_pass[a][b] = min(free_pass[a][b], x[3] / 2)
free_pass[b][a] = min(free_pass[b][a], x[3] / 2)
else:
free_pass[a][b] = min(free_pass[a][b], x[3])
free_pass[b][a] = min(free_pass[b][a], x[3])
for c in range(n):
for i in range(n):
for j in range(n):
cost[i][j] = min(cost[i][j], cost[i][c] + cost[c][j])
free_pass[i][j] = min(free_pass[i][j], free_pass[i][c] + free_pass[c][j])
c1, c2 = 0, r
for i in range(m - 1):
a, b = mapping[route[i]], mapping[route[i + 1]]
c1 += cost[a][b]
c2 += free_pass[a][b]
if c2 < c1:
print("Yes")
else:
print("No")
'Python > Coding Test' 카테고리의 다른 글
21277 짠돌이 호석 (0) | 2022.02.24 |
---|---|
10703 유성 (0) | 2022.02.24 |
1421 나무꾼 이다솜 (0) | 2022.02.23 |
2563 전깃줄 (0) | 2022.02.22 |
15728 에리 - 카드 (0) | 2022.02.22 |