특정한 최단 경로
이 문제는 다익스트라 문제로, 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]가 될것이고 나머지도 마찬가지이다.
Author And Source
이 문제에 관하여(특정한 최단 경로), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sezeom/다익스트라-특정한-최단-경로저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)