21940번: 가운데에서 만나기
위 조건을 만족하는 도시 $X$의 번호를 출력한다. 만약 가능한 도시 $X$가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다.
www.acmicpc.net
문제
준형이는 내일 친구들을 만나기로 했다. 준형이와 친구들은 서로 다른 도시에 살고 있다.
도시를 연결하는 도로는 일방 통행만 있어서 도시 에서 도시 로 가는 시간과 도시 에서 도시 로 가는 시간이 다를 수 있다.
준형이와 친구들은 아래 조건을 만족하는 도시 를 선택하여 거기서 만나려고 한다.
- 왕복시간은 자신이 살고 있는 도시에서 도시 로 이동하는 시간과 도시 에서 다시 자신이 살고 있는 도시로 이동하는 시간을 합한 것이다.
- 준형이와 친구들이 도로를 이용하여 갈 수 있는 도시만 선택한다.
- 준형이와 친구들의 왕복시간 들 중 최대가 최소가 되는 도시 를 선택한다.
- 준형이와 친구들이 이동할 수 있는 도시가 최소한 하나 이상이 있음을 보장한다.
도시가 많다보니 계산하기 힘들다. 준형이와 친구들을 대신하여 도시 를 알려주자.
입력
첫 번째 줄에는 도시의 개수 과 도로의 개수 이 주어진다.
두 번째 줄부터 M + 1줄까지 도시 , 도시 , 도시 에서 도시 로 이동하는데 걸리는 시간 가 공백으로 구분되어 주어진다.
가 주어진다.
줄에는 준형이와 친구들의 총 인원가 공백으로 구분되어 주어진다.
줄에는 준형이와 친구들이 살고 있는 도시의 번호출력
위 조건을 만족하는 도시 의 번호를 출력한다. 만약 가능한 도시 가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다.
제한
코드
n, m = map(int, input().split())
road = [[int(1e9)] * (n+1) for _ in range(n+1)]
for i in range(n+1): # 초기화
road[i][i] = 0
for _ in range(m):
a, b, t = map(int, input().split())
road[a][b] = t # 도시 a -> 도시 b로 가는데 걸리는 시간 t
k = int(input())
cities = list(map(int, input().split())) # 준형이와 친구들이 살고 있는 도시들
# 플로이드 워셜
for k in range(1, n+1):
for i in range(1, n+1):
for j in range(1, n+1):
if road[i][j] > (road[i][k]+road[k][j]):
road[i][j] = road[i][k]+road[k][j]
# 왕복시간이 최소가 되는 도시 찾기
ans = []
min_time = int(1e9)
for x in range(1, n+1):
tmp = 0
for c in cities:
tmp = max(road[c][x]+road[x][c], tmp)
if tmp < min_time:
ans = [x]
min_time = tmp
elif tmp == min_time:
ans.append(x)
print(*ans)
플로이드 워셜 알고리즘을 이용하여 각 마을에서 다른 마을까지의 모든 최단 경로를 구한다.
준형이와 친구들이 각자 사는 마을에서 각 마을까지의 왕복 거리(road[i][x]+road[x][i])를 구해보고 마을까지 최대 왕복거리가 최소인 마을을 찾아낸다.
'문제풀이 > 최단경로' 카테고리의 다른 글
[Python/파이썬] 백준 1446번 지름길 (0) | 2023.12.15 |
---|---|
[Python/파이썬] 백준 15723번 n단 논법 (0) | 2023.12.14 |
[Python/파이썬] 백준 16118번 달빛 여우 (1) | 2023.08.23 |
[Python/파이썬] 백준 1613번 역사 (0) | 2023.07.07 |
[Python/파이썬] 백준 11657번 타임머신 (0) | 2023.05.16 |