이 문제가 다익스트라 문제라는 것을 알았다면, 최소 경로를 지나갈 때 목적지 후보들 중에서 G <-> H의 경로를 지나는 경우가 최소가 되는 목적지를 구해야 한다는 것을 알 수 있다.
이 조건을 해결하기 위해서 크게 두 가지 방법을 사용할 수 있다.
정석적인 방법과 애드혹스러운 기교를 통해 문제를 해결하는 방법이 존재한다.
내가 푼 방법은 후자의 방법이지만 먼저 정석적인 방법을 간단히 소개해보면,
먼저 출발지를 시작으로 다익스트라를 통해 모든 노드를 잇는 최소 거리를 구한다.
H를 시작으로 다익스트라를 통해 모든 노드를 잇는 최소 거리도 구해준다.
[1번에서 구한 출발지로부터 G까지의 최소거리 + G -> H의 거리 + 2번에서 구한 H로부터 목적지까지 잇는 최소거리] 값을 구해준다.
목적지 중에서 3번의 값과 1번의값이 같다면 G - H 간선을 지나는 값이 최소 거리가 되어 정답이 될 것이다.
위 방법이 정해로 풀리지만 간선의 가중치가 양의 정수라는 조건을 이용한다면 조금 특별한 기교를 부릴 수 있다.
출발지를 시작으로 다익스트라를 수행하기 전에 G - H의 가중치를 아주 작은 값 0.1을 미리 빼준다.
간선의 가중치는 항상 양의 정수이고, G - H의 가중치를 0.1만큼 빼주었으니 출발지로부터 목적지로 이동할 수 있는 최단 경로가 G - H의 경로를 포함한 여러 가지일 경우 항상 G - H의 간선을 지나게 된다.
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')를 사용했다. 이 경우의 반례가 발생하는듯 한데, 아직도 잘 모르겠다..
