[BOJ] 9370 - 미확인 도착지 (Python)

 

 

아이디어

 

다익스트라를 이용해 목적지 후보에 도착하는 최단 시간과 g와 h 교차로를 거쳐 도착하는 최단 시간을 비교한다.

 

 

풀이

 

import sys
from heapq import heappush, heappop

input = sys.stdin.readline
INF = int(1e9)

def solution():
    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))
        X = [int(input()) for _ in range(t)]
        D = dict()
        res = []
        for i in [s, g, h]:
            D[i] = [INF]*(n+1)
            D[i][i] = 0
            heap = [(0, i)]
            while heap:
                d, idx = heappop(heap)
                if D[i][idx] < d:
                    continue
                for j, _d in graph[idx]:
                    if d+_d < D[i][j]:
                        D[i][j] = d+_d
                        heappush(heap, (d+_d, j))
        for x in X:
            min_d = min(D[s][g]+D[g][h]+D[h][x], D[s][h]+D[h][g]+D[g][x])
            if D[s][x] == min_d:
                res.append(x)
        print(*sorted(res))

solution()