백준 9370 미확인 도착지

과정

• S:시작점, G,H:지나간 곳, X:목적지후보
• S에서 X로 가는데, 최단 거리로 가는 중 G,H를 지나게 될 때의 X는 가능한 목적지가 된다.
• S-G-H-X, S-H-G-X 순서 중 최소인 거리가 S-X의 최단 거리보다 크면, 불가능한 목적지이다.

import sys
import heapq

tc = int(input())
INF = 1e9

def dijkstra(start):
    distance = [INF] * N
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if distance[i[0]] > cost:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
    return distance

for _ in range(tc):

    N, M, T = map(int, sys.stdin.readline().split())  # N교차로 M도로 T목적지후보 수

    S, G, H = map(int, sys.stdin.readline().split())  # S출발지 G -> H

    graph = [[] for _ in range(N)]
    for _ in range(M):
        A, B, D = map(int, sys.stdin.readline().split())
        graph[A - 1].append((B - 1, D))  # 도로 정보 (교차로, 거리)
        graph[B - 1].append((A - 1, D))

    start_dist = dijkstra(S - 1)

    mid1_dist = dijkstra(G - 1)[H - 1]

    ans = []
    for _ in range(T):
        yet_goal = int(input())
        end_dist = dijkstra(yet_goal - 1)
        end = min(end_dist[G - 1], end_dist[H - 1])


        if start_dist[yet_goal - 1] >= min(start_dist[H - 1] + mid1_dist + end_dist[G - 1],
                                           start_dist[G - 1] + mid1_dist + end_dist[H - 1]):
            ans.append(yet_goal)
    ans.sort()
    
    print(*ans)