[다익스트라/파이썬] 백준 9370번 : 미확인 도착지 / 골드 2

https://www.acmicpc.net/problem/9370

9370번: 미확인 도착지

import sys
import collections
import heapq

input = sys.stdin.readline

t = int(input())
for _ in range(t):

    n, m, t = map(int, input().split())  # 교차로, 도로, 목적지 후보 개수
    s, g, h = map(int, input().split())  # s 출발지, g -> h

    graph = collections.defaultdict(list)
    for _ in range(m):
        a, b, d = map(int, input().split())
        if [a,b] == [g,h] or [a,b] == [h, g]:
            graph[a].append([b, d - 0.5])
            graph[b].append([a, d - 0.5])
        else:
            graph[a].append([b, d])
            graph[b].append([a, d])

    candidates = []
    for _ in range(t):
        candidates.append(int(input()))

    dist = [[0, False] for _ in range(n)]
    visited = [False for _ in range(n)]

    q = []
    heapq.heappush(q, [0, s, False])

    while q:
        #print(q)
        cost, cur, gh = heapq.heappop(q)
        if not visited[cur-1]:
            visited[cur-1] = True
            dist[cur-1][0] = cost
            #print(cost, cur, gh)
            if gh:
                dist[cur-1][1] = True
            for next, w in graph[cur]:
                if cur == g and next == h:
                    heapq.heappush(q, [cost + w, next, True])
                elif cur == h and next == g:
                    heapq.heappush(q, [cost + w, next, True])
                elif gh:
                    heapq.heappush(q, [cost + w, next, True])
                else:
                    heapq.heappush(q, [cost + w, next, False])

    answer = []
    for c in candidates:
        if dist[c-1][1]:
            answer.append(c)
    print(*sorted(answer))

실수하기 쉬운 반례는

최단 경로가 여러개일 때 g-h를 거쳐가는 경로를 나중에 탐색했을 때

방문 여부 때문에 탐색이 막혀버리면 안된다. 

방지를 위해 g-h 구간의 거리를 임의로 0.5를 줄여준다.

그럼 최단 경로가 여러 개일 경우 g-h를 거쳐가는 경로를 택하게 된다.