BOJ - 21940 - 가운데에서 만나기

import sys
def solution():
    _INF = 1e9
    N, M = map(int, sys.stdin.readline().split())

    maps = [[0 if row == col else _INF for col in range(N)] for row in range(N)]

    for _ in range(M):
        A, B, T = map(int, sys.stdin.readline().split())
        maps[A-1][B-1] = min(maps[A-1][B-1], T)

    K = int(sys.stdin.readline())
    C = list(map(int, sys.stdin.readline().split()))

    for k in range(N):
        for i in range(N):
            for j in range(N):
                maps[i][j] = min(maps[i][j], maps[i][k] + maps[k][j])

    min_value = _INF
    result = []
    for city in range(N):
        temp = 0
        for friend in C:
            friend -= 1
            temp = max(temp, maps[friend][city] + maps[city][friend])
        
        if temp < min_value:
            min_value = temp
            result = [(city+1)]
        elif temp == min_value:
            result.append((city+1))

    print(*result)
    
solution()

https://www.acmicpc.net/problem/21940