https://www.acmicpc.net/problem/13424
문제분석
- 분류
- 그래프 이론, 다익스트라, 플로이드-워셜
- 문제설명
- N개의 방, M개의 비밀통로, K명의 친구들
- 모임에 참여하는 친구들은 N개의 방 중에서 한 군데씩에 각각 위치해있다.
- 이들은 항상 처음 위치에서 모임 장소까지의 이동 거리가 가장 짧은 경로만을 이용한다.
- 모임에 참석하는 친구들의 이동 거리의 총합이 최소가 되는 방을 오늘의 모임 장소로 사용한다.
- 친구들의 이동 거리의 총합이 최소가 되도록 하는 모임 장소를 찾아 출력하는 프로그램을 작성한다.
코드
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)))
|
문제풀이
- 다익스트라 알고리즘을 활용한다.
- adj에 입력 받은 데이터를 넣어 양방향 간선으로 표시한다.
- 반복문을 이용하여 n개의 방의 다익스트라를 구한다.
- i번 방에서 각 친구들의 방 위치까지 이동할 때의 최단 거리 합을 구하고, ans[i]에 i번 방까지의 친구들의 이동 거리의 총합을 저장한다.
- 가장 작은 총합 min을 구해 해당 방의 번호 index를 출력한다.
'Koala - 7기 > 코딩테스트 준비 스터디' 카테고리의 다른 글
[백준 / Python] 13424 - 비밀 모임 (0) | 2022.08.22 |
---|---|
[백준/python] 13549번 숨바꼭질 3 (0) | 2022.08.21 |
[백준/Python] 1504번: 특정한 최단 경로 (0) | 2022.08.21 |
[백준/C++] 1238번 파티 (0) | 2022.08.20 |
[백준/C++] 13549번 숨바꼭질 3 (0) | 2022.08.19 |