특정한 최단 경로

문제 설명

방향성 없는 그래프가 주어질 때 1부터 n까지 v1과 v2를 지나서 가는 최단 경로를 구하는 문제이다.

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

1504번: 특정한 최단 경로

문제 풀이

첫 번째 접근

다익스트라로 풀어주면 되지만 v1과 v2를 지나가야 한다는 것이 문제이다. 여기서 갈 수 있는 경로는 1에서 v1, v2, n이거나 1에서 v2, v1, n이다.

 

간단하게 생각해주면 되는데, 일단 1부터 시작하는 다익스트라와 v1, v2로 시작하는 다익스트라의 거리를 구해준다. 그리고 1에서 v1으로 v1에서 v2로 v2에서 n으로 가는 거리와 1에서 v2로 v2에서 v1으로 v1에서 n으로 구한 다익스트라의 거리를 더해서 제일 작은 것을 반환하면 된다.

 

여기서 조심할 점은 값이 안 나오면 -1을 반환하는 것이다. 그러므로 값이 maxInt보다 크거나 같다면 -1을 반환한다.

코드

python

import sys
import heapq

n, e = map(int, sys.stdin.readline().rstrip().split(" "))
graph = [[] for _ in range(n)]
maxInt = int(1e9)

for _ in range(e):
    a, b, c = map(int, sys.stdin.readline().rstrip().split(" "))
    a -= 1
    b -= 1
    graph[a].append([b, c])
    graph[b].append([a, c])

v1, v2 = map(int, sys.stdin.readline().rstrip().split(" "))
v1 -= 1
v2 -= 1


def dij(start):
    dp = [maxInt for _ in range(n)]
    hq = []
    dp[start] = 0
    heapq.heappush(hq, (dp[start], start))

    while hq:
        cost, node = heapq.heappop(hq)

        if cost > dp[node]:
            continue

        # 노드하고 연결 된 거 다 찾아야 한다.
        for current in graph[node]:
            index, newCost = current
            # 값이 0이 아니라는 의미는 분명 연결이 되어있다는 뜻
            if dp[index] > cost + newCost:
                dp[index] = cost + newCost
                heapq.heappush(hq, (dp[index], index))
    return dp


original = dij(0)
v1Dp = dij(v1)
v2Dp = dij(v2)

v1Tov2 = original[v1] + v1Dp[v2] + v2Dp[n-1]
v2Tov1 = original[v2] + v2Dp[v1] + v1Dp[n-1]
answer = min(v1Tov2, v2Tov1)
print(answer if answer < maxInt else -1)