문제

[백준] 미확인 도착지 (Gold 2)

요약

서커스 예술가들은 출발지에서 목적지 후보들 중 하나로 가고 있다. 그들은 목적지까지 최단 거리로 간다. 그들은 g-h 사이의 도로를 반드시 경유한다. 이 도로는 목적지 후보들 중 적어도 1개로 향하는 최단 경로의 일부이다.

목적지 후보들 중 불가능한 경우를 제외한 목적지들을 공백으로 분리시킨 오름차순 정수로 출력하라.

분류

  • 다익스트라

풀이

내 풀이 (다익스트라)

문제의 조건을 조합하면, 예술가들은 s-g-h-후보 혹은 s-h-g-후보 의 경로를 거쳐갔다. 결국 다음의 최단 경로들이 존재한다면 해당 후보 도착지에는 도달할 수 있다.

  1. s에서 g로 가는 경로
  2. s에서 h로 가는 경로
  3. h에서 후보 도착지로 가는 경로
  4. g에서 후보 도착지로 가는 경로

따라서 s, h, g를 출발지로 하는 데익스트라 알고리즘을 세 번 수행하고 최단거리의 유무를 판단해주면 되겠다.

import sys
from heapq import heappush, heappop
input = sys.stdin.readline
INF = sys.maxsize

T = int(input())

for _ in range(T):
    n, m, t = map(int, input().split())  # 교차로, 도로, 목적지 후보 개수
    s, g, h = map(int, input().split())  # 출발지, 냄새맡은 곳

    graph = [[] for _ in range(n)]

    for _ in range(m):
        a, b, d = map(int, input().split())
        graph[a - 1].append((b - 1, d))
        graph[b - 1].append((a - 1, d))

    arr = [int(input()) for _ in range(t)]  # 후보들

    d = [INF] * n
    d[s - 1] = 0

    queue = [(0, s - 1)]

    while queue:
        w, i = heappop(queue)

        if d[i] < w:
            continue

        for node, weight in graph[i]:
            if d[i] + weight < d[node]:
                d[node] = d[i] + weight
                heappush(queue, (d[node], node))

    d_g = [INF] * n
    d_g[g - 1] = 0

    queue = [(0, g - 1)]

    while queue:
        w, i = heappop(queue)

        if d_g[i] < w:
            continue

        for node, weight in graph[i]:
            if d_g[i] + weight < d_g[node]:
                d_g[node] = d_g[i] + weight
                heappush(queue, (d_g[node], node))

    d_h = [INF] * n
    d_h[h - 1] = 0

    queue = [(0, h - 1)]

    while queue:
        w, i = heappop(queue)

        if d_h[i] < w:
            continue

        for node, weight in graph[i]:
            if d_h[i] + weight < d_h[node]:
                d_h[node] = d_h[i] + weight
                heappush(queue, (d_h[node], node))

    arr.sort()
    ans = []
    for val in arr:
        if d[val - 1] == d_g[s - 1] + d_h[val - 1] + d_g[h - 1]:
            ans.append(val)
        elif d[val - 1] == d_h[s - 1] + d_g[val - 1] + d_g[h - 1]:
            ans.append(val)
    print(*ans)