[백준] 9370 - 미확인 도착지 (G2)

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

9370번: 미확인 도착지

한 노드에 대한 최단 경로에 특정 경로가 포함되어 있는지를 확인하는 문제이다.

 

아이디어는 어렵지 않은데, 구현이 복잡하다.

 

나는 처음에 다익스트라를 한번 돌리면서, 그 과정에 <g, h> 간선이 포함되는지를 체크하려고 하였다.

그런데 최단경로가 여러개인 경우, <g, h> 간선이 포함된 최단 경로를 먼저 고르는 것을 구현하기가 어려워서 이 방법은 포기했다. (나중에 난이도 기여 내역을 보니 이렇게 푼 사람도 있었다.)

 

그 다음 떠올린 간단한 방법은 다익스트라를 3번 돌리는 것이다.

s 부터 출발하는 다익스트라, g 부터 출발하는 다익스트라, h 부터 출발하는 다익스트라

 

이렇게 3개를 돌린 결과를 모두 저장한 뒤, 체크할 노드가 check 라고 하면

s -> check == s -> g + g -> h + h -> check

s -> check == s -> h + h -> g + g -> check

이렇게 2가지를 체크해서 둘 중 하나라도 해당되면 답으로 체크해주면 된다.

 

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

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+1)]
    check_dist = 0

    dist_for_h = [INF 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):
            check_dist = d

    # get dist for s
    pq = []
    dist_for_s = [INF for _ in range(n + 1)]
    dist_for_s[s] = 0
    heappush(pq, (0, s))
    visit = [False for _ in range(n + 1)]
    while pq:
        d, node = heappop(pq)

        if visit[node]:
            continue

        for next_node, next_dist in graph[node]:
            if not visit[next_node]:
                if dist_for_s[next_node] >= dist_for_s[node] + next_dist:
                    dist_for_s[next_node] = dist_for_s[node] + next_dist
                    heappush(pq, (dist_for_s[next_node], next_node))

        visit[node] = True

    # get dist for g
    pq = []
    visit = [False for _ in range(n+1)]
    dist_for_g = [INF for _ in range(n + 1)]
    dist_for_g[g] = 0
    heappush(pq, (0, g))
    while pq:
        d, node = heappop(pq)

        if visit[node]:
            continue

        for next_node, next_dist in graph[node]:
            if not visit[next_node]:
                if dist_for_g[next_node] >= dist_for_g[node] + next_dist:
                    dist_for_g[next_node] = dist_for_g[node] + next_dist
                    heappush(pq, (dist_for_g[next_node], next_node))

        visit[node] = True

    # get dist for h
    pq = []
    visit = [False for _ in range(n + 1)]
    dist_for_h = [INF for _ in range(n + 1)]
    dist_for_h[h] = 0
    heappush(pq, (0, h))
    while pq:
        d, node = heappop(pq)

        if visit[node]:
            continue

        for next_node, next_dist in graph[node]:
            if not visit[next_node]:
                if dist_for_h[next_node] >= dist_for_h[node] + next_dist:
                    dist_for_h[next_node] = dist_for_h[node] + next_dist
                    heappush(pq, (dist_for_h[next_node], next_node))

        visit[node] = True

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

    ans = []
    for node in check:
        if dist_for_s[node] == dist_for_s[g] + check_dist + dist_for_h[node]:
            ans.append(node)
        elif dist_for_s[node] == dist_for_s[h] + check_dist + dist_for_g[node]:
            ans.append(node)

    print(*ans)

똑같은 다익스트라를 3번 적어서 코드는 길지만 내용은 어렵지 않다.