백준 9370번: 미확인 도착지

백준 9370번: 임계경로

풀이 과정

g와 h 사이의 도로를 지났다면 출발지 -> g -> h -> 목적지 혹은 출발지 -> h -> g -> 목적지 둘 중 하나의 최단 거리가 출발지 -> 목적지의 최단 거리와 같아야 한다.

정답 코드

import sys
from heapq import heappush, heappop
from collections import defaultdict
input = sys.stdin.readline


def dijkstra(S):
    D = [float('inf')] * (n + 1)
    D[S] = 0

    Q = list()
    heappush(Q, (0, S))

    while Q:
        SD, SN = heappop(Q)
    
        if D[SN] < SD:
            continue

        for FN, FD in L[SN]:
            d = SD + FD
            if D[FN] > d:
                D[FN] = d
                heappush(Q, (d, FN))

    return D


for T in range(int(input())):
    n, m, t = map(int, input().split())
    s, g, h = map(int, input().split())
    L = defaultdict(list)
    for i in range(m):
        a, b, d = map(int, input().split())
        L[a].append((b, d))
        L[b].append((a, d))
    x = list(int(input()) for _ in range(t))
    
    a = list()
    S = dijkstra(s)
    G = dijkstra(g)
    H = dijkstra(h)
    for i in x:
        if (S[g] + G[h] + H[i] == S[i] or S[h] + H[g] + G[i] == S[i]) and S[i] != float('inf'):
            a.append(i)
    print(*sorted(a))

반성할 점

애초에 목적지에 도착 못 할 수도 있었다.. 그렇게 되면 inf + inf = inf 이므로.. 이것 때문에 30분을 헤맸다.