[Python] 백준 13424번: 비밀 모임

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

13424번: 비밀 모임

 

 > 접근

친구들이 위치한 방들의 리스트를 rooms라고 해보자. 모든 노드를 돌면서(for i 1~N) 'i에서 rooms까지 거리들의 총합'을 구하고, 이 값이 가장 작은 곳이 모임 장소가 된다. 이 때 dists[i][room]과 같은 코드가 필요하게 되는데, 이를 위해 '모든 곳에서 모든 곳까지의 최단경로'를 구하는 Floyd Warshall를 사용하게 된다.

 

import sys                        
input = sys.stdin.readline  
INF = 100001

if __name__ == '__main__':
  for _ in range(int(input())):
    # Input
    N, M = map(int, input().split())   
    
    dists = [[INF]*(N+1) for _ in range(N+1)]
    for _ in range(M):
      a, b, c = map(int, input().split())
      dists[a][b] = c
      dists[b][a] = c 
      
    int(input()) # K
    rooms = list(map(int, input().split()))


    # Floyd-Warshall
    for k in range(1, N+1):
      dists[k][k] = 0
      for i in range(1, N+1):
        for j in range(1, N+1):
          dists[i][j] = min(dists[i][j], dists[i][k] + dists[k][j])


    # Print minDistNode
    minDistSum = float('inf')
    minDistNode = 0

    for i in range(1, N+1):
      distSum = sum(dists[room][i] for room in rooms)
      if minDistSum > distSum:
        minDistSum = distSum
        minDistNode = i

    print(minDistNode)