[BOJ / Python] 13424 - 비밀 모임

문제 링크

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

13424번: 비밀 모임

---

풀이

• 다익스트라 알고리즘을 활용해 풀었습니다. (line 6~17)
• 인접 행렬 adj 에 양방향 간선을 표시해줍니다. (line 26~27)
• 반복문을 돌려 1부터 n 번 방까지 다익스트라를 구합니다. (line 30~32)
  • [해당 방(i) -> 각 친구들의 방 위치] 까지 이동할때의 최단 거리 합을 구합니다. (line 32)
  • ans[i]에는 i까지 친구들의 이동거리의 총합이 저장되어 있습니다.
• 가장 작은 총합을 구해(min) 해당 방의 번호(index)를 출력합니다. (line 33)

---

코드

from heapq import *
import sys

input = sys.stdin.readline

def dijkstra(s):
    cost = [float('inf')] * (n+1)
    hq = [[0, s]]
    cost[s] = 0
    while hq:
        t,x = heappop(hq)
        if cost[x] != t: continue
        for nx, nt in adj[x]:
            if cost[nx] > t+nt:
                cost[nx] = t+nt
                heappush(hq, [cost[nx], nx])
    return cost

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    ans = [float('inf')]*(n+1)
    adj = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b, c = map(int, input().split())
        adj[a].append([b, c])
        adj[b].append([a, c])
    k = int(input())
    friend = [*map(int, input().split())]
    for i in range(1, n+1):
        dist = dijkstra(i)
        ans[i] = sum(dist[f] for f in friend)
    print(ans.index(min(ans)))