난이도 : 골드 2
유형 : 최단경로
https://www.acmicpc.net/problem/9370

---

문제 접근

n 노드 개수, m 간선 개수, t 목적지 후보 개수 를 입력받고
s 출발 노드 g,h 노드 (g와 h를 잇는 간선을 지나감) 를 입력받는다.

그리고 간선 m개의 정보
a,b,d => a,b 노드 사이의 가중치 d의 간선 입력

목적지 후보의 개수 t개의 각 줄 마다 x를 입력받는다, x는 목적지 후보 노드

일때 목적지가 될 수 있는 노드의 번호를 찾는 문제이다.

즉,
출발노드와 목적지 노드(후보들), 그리고 무조건 지나친 간선 이 주어졌을 때
목적지 후보 노드 들 중 가능한 목적지 노드를 구하라! 하는 문제이다.

특정 출발지 노드 에서 모든 노드까지의 최단거리를 구하는 다익스트라 알고리즘을 사용해야 한다.

예제 그림을 크게 보자면 다음과 같다.

출발 노드가 2이고,
무조건 지나친 간선 1-3(3) , 그리고
목적지 후보 노드 중 5,6 이라면,

2에서 5까지 최단거리는 5지만 1-3을 거친 최단거리는 11이다 그러니 5는 목적지가 될 수 없다. 둘러가지 않았다는 전제가 있기 때문이다.

6을 보자면, 2에서 6까지의 최단거리가 애초에 1-3 간선을 이용한 6이기때문에 목적지에 해당된다.

즉 이 문제는 시작노드에서 목적지 후보노드까지의 최단거리가
g-h 간선을 거친 최단거리와 동일하냐 안하냐를 파악하는 문제이다.

다익스트라 알고리즘은 총 3번 돌리면 된다.
출발노드 -> 모든 노드 거리
g -> 모든 노드 거리
h -> 모든 노드 거리

그리고
1. s → x의 최단 거리를 먼저 구한다.
2. 다음 두 경로를 고려한다:

• s → g → h → x
• s → h → g → x

3. 위 경로 중 하나라도 최단 거리와 같으면, 이 목적지 후보 x는 정답이 된다!

---

해답 및 풀이

import heapq
import sys
input = sys.stdin.readline

INF = int(1e9)

def dijkstra(s, graph,n):
    distance = [INF] * (n + 1)
    distance[s] = 0 
    queue = []
    heapq.heappush(queue,(0, s))

    while queue:
        now_dist, now = heapq.heappop(queue) 

        if distance[now] < now_dist:
            continue

        for next_node, next_weight in graph[now]:
            cost = now_dist + next_weight

            if cost < distance[next_node]:
                distance[next_node] = cost
                heapq.heappush(queue, (cost, next_node))

    return distance


T = int(input())

for _ in range(T):

    result = []

    # 총 노드 개수, 간선 개수, 목적지 후보 노드 개수
    n, m, t = map(int,input().split())

    # 시작 노드, 무조건 지나는 노드 g, h 
    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))
        if (a == g and b == h) or (a == h and b == g):
            gh_weight = d  # g-h 간선의 거리 저장
    
    distance_s = dijkstra(s, graph, n)
    distance_g = dijkstra(g, graph, n)
    distance_h = dijkstra(h, graph, n)

    destinations = []
    for _ in range(t):
        x = int(input())
        destinations.append(x)
    
    for x in destinations:
        # s-> g -> h -> x
        path1 = distance_s[g] + gh_weight + distance_h[x]
        # s-> h -> g -> x
        path2 = distance_s[h] + gh_weight + distance_g[x]

        if distance_s[x] == path1 or distance_s[x] == path2:
            result.append(x)


    print(*sorted(result))

---

왜 distance_g[h] 나 distance_h[g] 를 쓰지 않고
굳이 gh_weight 를 따로 저장해서 써야 했을까?

gh_weight는 문제에서 "반드시 지나야 하는 g-h 간선"을 명시적으로 포함시키기 위한 장치이다.
다익스트라 결과로는 그걸 보장할 수 없기 때문에,
직접 간선 입력에서 찾아서 강제로 더해 구현하였다.