[파이썬] [최단경로] 백준 9370 미확인 도착지

문제

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

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 특정한 최단 경로"와 유사한 문제