이번 문제는 다익스트라 알고리즘을 통해 해결하였다. 그래프는 양방향 인접 리스트로 구현하였다. 이 문제에서는 친구들의 위치를 시작으로 하는 모든 방까지의 최소 거리를 저장하고, 전체 친구들의 위치에서 해당 방까지의 거리의 합을 따로 관리해야 한다. 전체 친구들의 위치로부터 방까지의 거리의 합을 distance라는 리스트에 저장하였다. 그리고 친구 한명 한명에 대한 최소 거리를 저장하기 위한 리스트 dist를 각 친구에 대하여 탐색할때마다 새로 선언해주면서 최소 거리를 저장하고 너비우선탐색을 마치고 나면 distance의 해당 인덱스에 값을 더해주는 방식으로 접근하였다. 너비우선탐색의 while문에서 각 dist에 여러개의 값이 가능할 경우 작은 값을 취하도록 하였다. 마지막에는 distance 리스트를 순회하며 가장 작은 값의 인덱스를 찾아 출력하였다.

• t를 입력받는다.
• t번 반복하는 for문을 돌린다.
  -> n, m을 입력받는다.
  -> 그래프를 나타낼 리스트 graph를 2차원 리스트로 선언한다.
  -> m번 반복하는 for문을 돌린다.
  --> a, b, c를 입력받는다.
  --> graph[a]에 (b, c)를 넣는다.
  --> graph[b]에 (a, c)를 넣는다.
  -> k를 입력받는다.
  -> 친구들의 위치에 해당하는 리스트 friend를 입력받는다.
  -> 친구들 전체 거리의 합을 저장하는 리스트 distance를 0 n+1개로 채운다.
  -> friend를 순회하는 i에 대한 for문을 돌린다.
  --> 친구 하나 하나에서의 최소 거리를 저장할 리스트 dist를 sys.maxsize n+1개로 채운다.
  --> 큐로 사용할 리스트 q를 최소힙으로 선언한다.
  --> dist[i]를 0으로 갱신한다.
  --> q가 있을 동안 반복하는 while문을 돌린다.
  ---> length, cur을 q에서 추출한다.
  ---> 만약 length가 dist[cur]보다 클 경우, 다음으로 넘어간다.
  ---> graph[cur]을 순회하는 nxt, l에 대한 for문을 돌린다.
  ----> tmp에 length+l을 저장한다.
  ----> 만약 tmp가 dist[nxt]보다 작을 경우,
  -----> dist[nxt]를 tmp로 갱신한다.
  -----> q에 (tmp, nxt)를 넣는다.
  --> 1부터 n까지 반복하는 j에 대한 for문을 돌린다.
  ---> distance[j]에 dist[j]를 더한다.
  -> 최소 거리의 방을 저장할 변수 result를 0으로 선언한다.
  -> 거리의 최솟값을 저장할 변수 mn을 sys.maxsize로 선언한다.
  -> 1부터 n까지 반복하는 i에 대한 for문을 돌린다.
  --> 만약 mn이 distance[i]보다 작을 경우,
  ---> mn을 distance[i]로 갱신한다.
  ---> result를 i로 갱신한다.
  -> i를 출력한다.

Code

import sys
import heapq
t=int(input())
for _ in range(t):
    n, m=map(int, input().split())
    graph=[[] for _ in range(n+1)]
    for _ in range(m):
        a, b, c=map(int, input().split())
        graph[a].append((b, c))
        graph[b].append((a, c))
    k=int(input())
    friend=list(map(int, input().split()))
    distance=[0 for _ in range(n+1)]
    for i in friend:
        dist = [sys.maxsize for _ in range(n + 1)]
        q=[]
        heapq.heappush(q, (0, i))
        dist[i]=0
        while q:
            length, cur=heapq.heappop(q)
            if length>dist[cur]:
                continue
            for nxt, l in graph[cur]:
                tmp=length+l
                if tmp<dist[nxt]:
                    dist[nxt]=tmp
                    heapq.heappush(q, (tmp, nxt))
        for j in range(1, n+1):
            distance[j]+=dist[j]
    result=0
    mn=sys.maxsize
    for i in range(1, n+1):
        if mn>distance[i]:
            mn=distance[i]
            result=i
    print(result)