BOJ - 13424 - 비밀 모임

Updated:

import sys

_INF = 1e9
def solution():
    T = int(input())
    for _ in range(T):
        N, M = map(int, sys.stdin.readline().split())
        Floyd = [[_INF for _ in range(N)] for _ in range(N)]
        for _ in range(M):
            a, b, c = map(int, sys.stdin.readline().split())
            Floyd[a-1][b-1] = c
            Floyd[b-1][a-1] = c
        K = int(input())
        arr = list(map(int, sys.stdin.readline().split()))

        for k in range(N):
            for i in range(N):
                for j in range(N):
                    if i == j:
                        Floyd[i][j] = 0
                        continue
                    Floyd[i][j] = min(Floyd[i][j], Floyd[i][k] + Floyd[k][j])

        temp = _INF
        retIdx = -1
        for i in range(N):
            distance = 0
            for j in range(K):
                distance += Floyd[i][arr[j] - 1]

            if distance < temp:
                retIdx = i + 1
                temp = distance
        print(retIdx)
solution()

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

Categories:

Updated:

Leave a comment