1. 문제 설명

미확인 도착지

2. 문제 분석

양방향 그래프가 주어진다. 시작 노드 s에서 여러 목적지들 goals이 주어질 때, 해당 goal까지 가는 경로에 간선 g-h를 사용했는지 확인하고, g-h가 사용되지 않았다면 예상 가능 목적지에서 제외한다.

• s-goal에 g-h 또는 h-g 간선이 사용되었는지 어떻게 확인할 수 있을까? 이때 s-goal까지 가는 데 사용된 간선이 최단 경로라는 점을 생각해보면, s->g->h->goal 또는 s->h->g->goal 최단 경로의 합과 s->goal의 값이 같을 때에만 최단 경로 중 g-h가 사용되었다고 볼 수 있다. 다익스트라 알고리즘을 통해 각 시작 노드(s, g, h)부터 모든 노드에 대한 최단 거리를 얻은 뒤 합계를 비교해 목적지를 카운트하자.

3. 나의 풀이

import heapq
import sys

t_case = int(sys.stdin.readline().rstrip())
INF = int(1e9)
for _ in range(t_case):
    n, m, t = map(int, sys.stdin.readline().rstrip().split())
    s, g, h = map(int, sys.stdin.readline().rstrip().split())
    nodes = [[] for _ in range(n+1)]
    goals = []
    for _ in range(m):
        tail, head, cost = map(int, sys.stdin.readline().rstrip().split())
        nodes[tail].append([head, cost])
        nodes[head].append([tail, cost])
        # 양방향 그래프 구현
    for _ in range(t):
        goals.append(int(sys.stdin.readline().rstrip()))

    def dijkstra(start):
        distances = [INF for _ in range(n+1)]
        distances[start] = 0
        pq = []
        heapq.heappush(pq, [0, start])

        while pq:
            cur_cost, cur_node = heapq.heappop(pq)

            if distances[cur_node] < cur_cost: continue

            for next_node, next_cost in nodes[cur_node]:
                if distances[next_node] > cur_cost + next_cost:
                    distances[next_node] = cur_cost + next_cost
                    heapq.heappush(pq, [cur_cost+next_cost, next_node])
        return distances

    distances_s = dijkstra(s)
    distances_g = dijkstra(g)
    distances_h = dijkstra(h)

    s_to_g = distances_s[g]
    s_to_h = distances_s[h]
    g_to_h = distances_g[h]
    h_to_g = distances_h[g]

    result = []
    for goal in goals:
        # s -> g, g -> h, h -> goal
        # s -> h, h -> g, g -> goal
        # g-h 간선을 사용해 해당 goal에 도착한 거리가 s->goal까지의 최단 거리와 같다면 goal까지 가는 데 g-h를 사용하였음
        if distances_s[goal] == s_to_g + g_to_h + distances_h[goal]:
            result.append(goal)
        elif distances_s[goal] == s_to_h + h_to_g + distances_g[goal]:
            result.append(goal)

    result.sort()
    print(*result, sep=' ')