[백준 1504] 특정한 최단 경로

 

 

문제

---

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

1504번: 특정한 최단 경로

 

 

나의 풀이

---

방법은 두 가지가 있다.

s -> v1 -> v2 -> n

s -> v2 -> v1 -> n

각 경로가 최소가 되는 것을 찾으면 최종경로 또한 최소가 된다. 따라서 s, v1, v2를 시작점으로 해서 다익스트라 알고리즘을 3번 돌린 뒤에 위 두 경로 중 최단거리를 print하면 된다.

 

코드

---

# https://www.acmicpc.net/problem/1504
import sys
input = sys.stdin.readline
import heapq
inf = sys.maxsize

N, E = map(int, input().split())
arr = [[] for _ in range(N+1)]

for _ in range(E):
    a, b, c = map(int, input().split())
    arr[a].append([b, c])
    arr[b].append([a, c])
v1, v2 = map(int, input().split())


def dijkstra(start):
    dp = [inf for _ in range(N+1)]
    dp[start] = 0
    hq = []
    heapq.heappush(hq, [0,start])
    while hq:
        w, c = heapq.heappop(hq)
        for n_n, n_w in arr[c]:
            wei = n_w + w
            if dp[n_n] > wei:
                dp[n_n] = wei
                heapq.heappush(hq, [wei, n_n])
    return dp

one = dijkstra(1)
v1_ = dijkstra(v1)
v2_ = dijkstra(v2)
ans = min(one[v1]+v1_[v2]+v2_[N], one[v2]+v2_[v1]+v1_[N])
print(ans if ans<inf else -1)