[백준] 1504. 특정한 최단 경로 (Python)

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

1504번: 특정한 최단 경로

 

🔥 주어진 두 정점을 반드시 통과해야 하므로 다음과 같이 두 경우로 나누어 계산하였다.

🔥 시작점 ➡️ 정점 1 ➡️ 정점 2 ➡️ 끝점

🔥 시작점 ➡️ 정점 2 ➡️ 정점 1 ➡️ 끝점

🔥 두 경우 중 가장 작은 값이 정답!

 

import heapq
import sys

N, E = map(int, sys.stdin.readline().split())

board = [[] for _ in range(N+1)]

for _ in range(E):
    a, b, c = map(int, sys.stdin.readline().split())
    board[a].append((b, c))
    board[b].append((a, c))

m1, m2 = map(int, sys.stdin.readline().split())

def dijkstra(start):
    heap = []
    heapq.heappush(heap, (0, start)) # 비용, 경유지
    result = [2e18] * (N + 1)
    result[start] = 0
    while heap:
        cost, now = heapq.heappop(heap)
        if cost > result[now]:
            continue
        for b in board[now]:
            newcost = cost+b[1]
            if newcost < result[b[0]]:
                result[b[0]] = newcost
                heapq.heappush(heap, (newcost, b[0]))
    return result

# 1 -> m1 -> m2 -> N
# 1 -> m2 -> m1 -> N

res_one = dijkstra(1)
res_m1 = dijkstra(m1)
res_m2 = dijkstra(m2)

ans = min(res_one[m1]+res_m1[m2]+res_m2[N], res_one[m2]+res_m2[m1]+res_m1[N])

if ans < 2e18:
    print(ans)
else:
    print(-1)