[백준/파이썬] 9370번 미확인 도착지

문제 주소: https://www.acmicpc.net/problem/9370

9370번: 미확인 도착지

문제 해석

문제 풀이

이 문제가 다익스트라 문제라는 것을 알았다면, 최소 경로를 지나갈 때 목적지 후보들 중에서 G <-> H의 경로를 지나는 경우가 최소가 되는 목적지를 구해야 한다는 것을 알 수 있다.

이 조건을 해결하기 위해서 크게 두 가지 방법을 사용할 수 있다.

정석적인 방법과 애드혹스러운 기교를 통해 문제를 해결하는 방법이 존재한다.

내가 푼 방법은 후자의 방법이지만 먼저 정석적인 방법을 간단히 소개해보면,

1. 먼저 출발지를 시작으로 다익스트라를 통해 모든 노드를 잇는 최소 거리를 구한다.
2. H를 시작으로 다익스트라를 통해 모든 노드를 잇는 최소 거리도 구해준다.
3. [1번에서 구한 출발지로부터 G까지의 최소거리 + G -> H의 거리 + 2번에서 구한 H로부터 목적지까지 잇는 최소거리] 값을 구해준다.
4. 목적지 중에서 3번의 값과 1번의값이 같다면 G - H 간선을 지나는 값이 최소 거리가 되어 정답이 될 것이다.

위 방법이 정해로 풀리지만 간선의 가중치가 양의 정수라는 조건을 이용한다면 조금 특별한 기교를 부릴 수 있다.

1. 출발지를 시작으로 다익스트라를 수행하기 전에 G - H의 가중치를 아주 작은 값 0.1을 미리 빼준다.
2. 간선의 가중치는 항상 양의 정수이고, G - H의 가중치를 0.1만큼 빼주었으니 출발지로부터 목적지로 이동할 수 있는 최단 경로가 G - H의 경로를 포함한 여러 가지일 경우 항상 G - H의 간선을 지나게 된다.
3. 2번의 조건에 의해 최소 거리가 부동소수점을 가지게 된다면 G - H 간선을 지나게 됨을 알 수 있고, 해당 목적지가 정답이 된다.

 

문제 코드

import sys
import heapq

input = sys.stdin.readline


######################### solve ###############################
def solve():
    n, m, target_len = map(int, input().split())
    start, node1, node2 = map(int, input().split())

    adj = [[] for _ in range(n + 1)]
    visit = [100000000] * (n + 1)
    targets = []

    for _ in range(m):
        a, b, c = map(int, input().split())
        # g -> h 교차로를 지나는 cost를 -0.1 해주어 동일한 cost일 때 항상 지나도록
        if (a == node1 and b == node2) or (a == node2 and b == node1):
            c -= 0.1
        adj[a].append([b, c])
        adj[b].append([a, c])

    for _ in range(target_len):
        targets.append(int(input()))

    # 다익
    hq = []
    heapq.heappush(hq, [0, start])
    visit[start] = 0
    while hq:
        cur_cost, cur_node = heapq.heappop(hq)
        if cur_cost != visit[cur_node]:
            continue
        for next_node, mcost in adj[cur_node]:
            moving_cost = cur_cost + mcost
            if visit[next_node] > moving_cost:
                visit[next_node] = moving_cost
                heapq.heappush(hq, [moving_cost, next_node])

    answer = []
    for target in targets:
        # float라면 지나야할 곳을 지난 것
        if isinstance(visit[target], float):
            answer.append(target)
    return sorted(answer)


###############################################################

t = int(input())
for _ in range(t):
    ans = solve()
    if ans:
        print(*ans)

제출 결과

다익스트라를 돌릴 때 최소 거리를 설정해주기 위해 float('inf')를 사용했다.
이 경우의 반례가 발생하는듯 한데, 아직도 잘 모르겠다..