[BOJ/백준] 21940 가운데에서 만나기

import sys
 
input = sys.stdin.readline
 
N,M = map(int,input().split())
 
 
INF = float('inf')
graph = [[0 if x == y else INF for y in range(N+1)] for x in range(N+1)]
 
for _ in range(M):
    x,y,pay = map(int,input().split())
 
    graph[x][y] = min(graph[x][y],pay)
 
 
 
 
for mid in range(1,N+1):
    for end in range(1,N+1):
        for start in range(1,N+1):
            if graph[start][end] > graph[start][mid] + graph[mid][end]:
                graph[start][end] = graph[start][mid] + graph[mid][end]
 
K = int(input())
friend_list = list(map(int,input().split()))
min_value = INF
min_list = []
for city in range(1,N+1):
    temp_max = 0
    for p_num in friend_list:
        if graph[p_num][city] + graph[city][p_num] > temp_max:
            temp_max = graph[p_num][city] + graph[city][p_num]
 
    if temp_max < min_value:
        min_value = temp_max
        min_list = [city]
    elif temp_max == min_value:
        min_list.append(city)
 
print(*min_list)

 이 문제는 플로이드와샬을 이용해 모든 경로에 대해 이동비용을 먼저 계산을 해준다.

 

 

그리고 전체 도시들을 for문을 돌리면서, 친구들의 이동비용을 구하고,

 

각 친구들의 이동비용의 최대값의 최소가 되는 경우를 구해서 출력해주면 된다.