특정한 최단 경로

백준 1504

이 문제는 다익스트라 문제로, 1번부터 N번까지 최단경로로 이동해야하는데, 특정한 두 점을 반드시 지나서 가야한다.

특정한 두 점 x, y가 있을 때의 최단경로는 1-x-y-N일 수도 있고 1-y-x-N일 수도 있으므로 두 경우를 모두 구하여 최솟값을 출력하면 된다.

즉 첫번째 경우에서 1에서 x까지의 최단경로 + x에서 y까지의 최단경로 + y에서 N까지의 최단경로를 모두 합해야한다.

import heapq
import sys

def dks(start):
    dp = [1e9]*(n+1)
    dp[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        wei, node = heapq.heappop(q)

        for ad_n, ad_w in graph[node]:
            ww = dp[node] + ad_w
            if ww < dp[ad_n]:
                dp[ad_n] = ww
                heapq.heappush(q, (ww, ad_n))

    return dp

n, e = map(int, sys.stdin.readline().split())
graph = [[]*(n+1) for _ in range(n+1)]

for _ in range(e):
    a, b, w = map(int, sys.stdin.readline().split())
    graph[a].append((b, w))
    graph[b].append((a, w))

x, y = map(int, sys.stdin.readline().split())

result = min(dks(1)[x]+dks(x)[y]+dks(y)[n], dks(1)[y]+dks(y)[x]+dks(x)[n])

if result < 1e9:
    print(result)
else:
    print("-1")

dp테이블은 start에서 dp인덱스 번째까지의 최단경로를 적어둔 테이블이므로 1에서 x까지의 최단경로는 dks(1)[x]가 될것이고 나머지도 마찬가지이다.