문제

(취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익)

어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다행히도 당신은 후각이 개만큼 뛰어나다. 이 후각으로 그들이 g와 h 교차로 사이에 있는 도로를 지나갔다는 것을 알아냈다.

이 듀오는 대체 어디로 가고 있는 것일까?

# 9370
import sys
input = lambda : sys.stdin.readline().strip()
INF = int(1e9)

import heapq
T = int(input())

def dijkstra(start):
    q = []
    distance = [INF] * (n+1)
    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 cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
    return distance
        

for _ in range(T):
    n, m, t = map(int, input().split())
    s, g, h = map(int, input().split())
    
    graph_normal = [[] for _ in range(n+1)]
    graph_not_gh = [[] for _ in range(n+1)]
    dist_gh = 0
    
    for _ in range(m):
        a, b, d = map(int, input().split())
        graph_normal[a].append((b, d))
        graph_normal[b].append((a, d))
        if (a == g and b == h) or (a == h and b == g):
            dist_gh = d
            continue
        graph_not_gh[a].append((b, d))
        graph_not_gh[b].append((a, d))
        
    target = []
    for _ in range(t):
        target.append(int(input()))
        
    result = []
    for i in target:
        # s -> 목적지
        graph = graph_normal
        dist_si = dijkstra(s)[i]
        
        # s -> g , s -> h
        graph = graph_not_gh
        dist_s = dijkstra(s)
        dist_sg = dist_s[g]
        dist_sh = dist_s[h]
        dist_hi = dijkstra(h)[i]
        dist_gi = dijkstra(g)[i]
        
        # s -> g -> h -> 목적지
        dist_sghi = dist_sg + dist_gh + dist_hi
        
        # s -> h -> g -> 목적지
        dist_shgi = dist_sh + dist_gh + dist_gi
        
        if dist_sghi == dist_si or dist_shgi == dist_si:
            result.append(i)
    
    result.sort()
    print(*result)

백준 9370 미확인 도착지