[백준 알고리즘] 13424번: 비밀 모임 (Python)

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

13424번: 비밀 모임

 

소스코드

import sys
import heapq as hq
input = sys.stdin.readline

def dijkstra(start):
  min_dis = [int(1e9)] *(n+1)
  q = []
  hq.heappush(q,[0,start])
  min_dis[start] = 0

  while q:
    cur_dis,cur_node = hq.heappop(q)

    if min_dis[cur_node] < cur_dis:
      continue

    for next_node, next_dis in graph[cur_node]:
      distance = cur_dis + next_dis
      if min_dis[next_node] > distance:
        min_dis[next_node] = distance
        hq.heappush(q,[distance,next_node])

  return min_dis

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())
  result = 2147000000
  num = 0
  friends = [0] + list(map(int,input().split()))
  ans = [[] for _ in range(n+1)]
  # 각각의 친구가 있는 방에서부터 1 ~ n번까지의 모든 거리를 구해줌 
  for i in range(1,k+1):
    t = dijkstra(friends[i])
    for j in range(1,n+1):
      ans[j].append(t[j])

  for idx,value in enumerate(ans[1:]):
    plus = sum(value)
    if plus < result:
      result = plus
      num = idx

  print(num+1)

 

풀이

★ 친구들이 있는 방에서부터 1 ~ n번 방까지의 거리를 모두 구해준 뒤, 각 방마다 각각의 친구가 갈 수 있는 거리의 합을 계산해줍니다. 그 후 방마다 거리의 합을 비교하여, 친구들이 최소로 도달할 수 있는 방의 번호를 출력해줍니다 :)