문제 링크
https://www.acmicpc.net/problem/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)))
'Koala - 5기 > 코딩테스트 준비 스터디' 카테고리의 다른 글
BOJ 1504(python) : 특정한 최단 경로 (0) | 2022.02.28 |
---|---|
[BOJ / Swift & Python] 23354 - 군탈체포조 (0) | 2022.02.27 |
[BOJ / Python] 13911번: 집 구하기 (0) | 2022.02.26 |
[BOJ/C++] 2615 - 오목 (0) | 2022.02.25 |
[BOJ / JAVA] 1504 - 특정한 최단 경로 (0) | 2022.02.21 |