문제
https://www.acmicpc.net/problem/9370
코드
import heapq
import sys
INF=sys.maxsize
def dijk(start):
dis = [INF] * (n+1)
q=[]
heapq.heappush(q,(0,start))
dis[start]=0
while q:
cost,node=heapq.heappop(q)
if cost>dis[node]:
continue
for i in graph[node]:
new_cost=cost+i[1]
if new_cost<dis[i[0]]:
dis[i[0]]=new_cost
heapq.heappush(q,(new_cost,i[0]))
return dis
T=int(input())
for _ in range(T):
n,m,t=map(int, input().split())
s,g,h=map(int, input().split())
graph=[[] for _ in range(n+1)]
for _ in range(m):
a,b,d=map(int, input().split())
graph[a].append([b,d])
graph[b].append([a,d])
target=[]
for _ in range(t):
target.append(int(input()))
s_=dijk(s)
h_=dijk(h)
g_=dijk(g)
result=[]
for i in target:
if s_[i]==s_[g]+g_[h]+h_[i] or s_[i]==s_[h]+h_[g]+g_[i]:
result.append(i)
result.sort()
for i in result:
print(i, end=' ')
생각 정리
g와 h를 무조건 지나야 한다면 두가지 방법이 있다.
출발지점 -> g -> h -> 도착지점 혹은
출발지점 -> h -> g -> 도착지점 이 될 수 있다.
이 두가지의 최단 거리를 구해주고 그 최단거리중 하나가
출발지점 -> 도착지점의 최단거리와 같다면 도착지점을 저장해준다.
"백준 1504 특정한 최단 경로"와 유사한 문제
'문제풀이 > 최단경로' 카테고리의 다른 글
[파이썬] [최단경로] 백준 14938 서강그라운드 (0) | 2022.03.16 |
---|---|
[파이썬] [최단경로] 백준 1956 운동 (0) | 2022.02.26 |
[파이썬] [최단경로] 백준 1504 특정한 최단 경로 (0) | 2022.02.26 |
[파이썬] [최단경로] 백준 11657 타임머신 (0) | 2022.02.09 |
[파이썬] [최단경로] 벨먼포드 (0) | 2022.02.09 |