*문제 출처는 백준에 있습니다.
문제 제목: 미확인 도착지 / 9370번 (골드 2단계)
문제 사이트: https://www.acmicpc.net/problem/9370
문제 설명

나의 풀이
import heapq
INF = 10**15
def dijkstra(start):
dist = [INF] * (n + 1)
dist[start] = 0 # 시작 지점은 0
heap = []
heapq.heappush(heap, (0, start)) # 가중치, 시작 노드
while heap:
current_dis, current_node = heapq.heappop(heap)
# 더 큰 경우는 제외
if current_dis > dist[current_node]:
continue
for next_node, next_dis in graph[current_node]:
# 더 작아야 탐색함
if current_dis + next_dis < dist[next_node]:
dist[next_node] = current_dis + next_dis
heapq.heappush(heap, (current_dis + next_dis, next_node))
return dist
if __name__=="__main__":
T = int(input())
result = []
for _ in range(T):
n, m, t = map(int, input().split())
s, g, h = map(int, input().split())
graph = {i: [] for i in range(1, n + 1)}
for _ in range(m):
a, b, d = map(int, input().split())
graph[a].append((b, d))
graph[b].append((a, d))
# g_h는 필연적으로 지나가야함
if (a == g and b == h) or (a == h and b == g):
w_gh = d
candidates = [int(input().strip()) for _ in range(t)]
candidates.sort()
# 다익스트라 3회
distS = dijkstra(s)
distG = dijkstra(g)
distH = dijkstra(h)
ans = []
for x in candidates:
# s->g->(g-h)->h->x vs s->h->(g-h)->g->x
cand1 = distS[g] + w_gh + distH[x]
cand2 = distS[h] + w_gh + distG[x]
if distS[x] == min(cand1, cand2):
ans.append(x)
print(*ans)

※ 알아야 할 것
for x in candidates:
# s->g->(g-h)->h->x vs s->h->(g-h)->g->x
cand1 = distS[g] + w_gh + distH[x]
cand2 = distS[h] + w_gh + distG[x]
if distS[x] == min(cand1, cand2):
ans.append(x)
이게 핵심 입니다!!!
'Coding Test > 백준-Python' 카테고리의 다른 글
| 백준 / 전기 요금 / 5710번 / Python (0) | 2025.10.16 |
|---|---|
| 백준 / 안녕 / 1535번 / Python (0) | 2025.10.14 |
| 백준 / 욕심쟁이 판다 / 1937번 / Python (0) | 2025.09.12 |
| 백준 / 텔레포트 / 16958번 / Python (1) | 2025.09.10 |
| 백준 / 얼음 미로 / 20926번 / Python (0) | 2025.09.09 |