문제

준형이는 내일 친구들을 만나기로 했다. 준형이와 친구들은 서로 다른 도시에 살고 있다.

도시를 연결하는 도로는 일방 통행만 있어서 도시 $A_{i}$에서 도시 $B_{i}$로 가는 시간과 도시 $B_{i}$에서 도시 $A_{i}$로 가는 시간이 다를 수 있다.

준형이와 친구들은 아래 조건을 만족하는 도시 $X$를 선택하여 거기서 만나려고 한다.

• 왕복시간은 자신이 살고 있는 도시에서 도시 $X$로 이동하는 시간과 도시 $X$에서 다시 자신이 살고 있는 도시로 이동하는 시간을 합한 것이다.
• 준형이와 친구들이 도로를 이용하여 갈 수 있는 도시만 선택한다.
• 준형이와 친구들의 왕복시간 들 중 최대가 최소가 되는 도시 $X$를 선택한다.
• 준형이와 친구들이 이동할 수 있는 도시가 최소한 하나 이상이 있음을 보장한다.

도시가 많다보니 계산하기 힘들다. 준형이와 친구들을 대신하여 도시
$X$를 알려주자.

# 21940
import sys
input = lambda : sys.stdin.readline().strip()
INF = int(1e9)

n, m = map(int, input().split())
graph = [[INF] * (n+1) for _ in range (n+1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = c

for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
            
for i in range(1, n+1):
    graph[i][i] = 0
            
k = int(input())
friend = list(map(int, input().split()))

friend_dist = []
for i in range(1, n+1):
    dist = []
    for f in friend:
        dist.append(graph[f][i] + graph[i][f])
    max_dist = max(dist)
    if max_dist >= INF:
        max_dist = 0
    friend_dist.append(max_dist)
    
min_dist = min(friend_dist)
for i in range(n):
    if friend_dist[i] == min_dist:
        print(i+1, end = " ")

백준 21940 가운데에서 만나기