문제
https://www.acmicpc.net/problem/21940
접근
- 모든 도시 간의 거리가 필요하므로 플로이드-워셜을 이용했다.
- 플로이드-워셜로 모든 도시 간의 거리를 구한 후, 각 도시에 대해 왕복시간의 최댓값을 계산했다.
풀이
- 주의할 점은 도시 a에서 도시 b로 가는 경로가 여러번 입력될 수 있으므로, 입력받을 때 경로의 최솟값으로 갱신해주어야 한다.
n, m = map(int, input().split())
dist = [[1e9] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
dist[i][i] = 0
for _ in range(m):
a, b, t = map(int, input().split())
dist[a][b] = min(dist[a][b], t)
for k in range(1, n + 1):
for j in range(1, n + 1):
for i in range(1, n + 1):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
k = int(input())
cities = list(map(int, input().split()))
min_cost = 1e9
ans = []
for i in range(1, n + 1):
cost = 0
for c in cities:
cost = max(cost, dist[c][i] + dist[i][c])
if cost < min_cost:
ans = [i]
min_cost = cost
elif cost == min_cost:
ans.append(i)
print(*ans)
'Python > Coding Test' 카테고리의 다른 글
19844 단어 개수 세기 (0) | 2022.03.07 |
---|---|
22943 수 (0) | 2022.03.01 |
4803 트리 (0) | 2022.03.01 |
19641 중첩 집합 모델 (0) | 2022.02.28 |
22871 징검다리 건너기 (large) (0) | 2022.02.27 |