[백준] 1504번-(Python 파이썬) - Dijkstra

문제링크 : https://www.acmicpc.net/problem/1504

이번 문제는 방향성이 없는 그래프에서 두개의 정점을 지날 때의 최단 거리를 구하는 문제이다.
v1, v2 두 정점을 지나서 n번 정점으로 가야하는데 처음에 무조건 순서대로 v1을 지나고 v2를 지나야 하는 줄 알고 문제를 제출하여 왜 틀렸었는지 몰라 계속하여 고민하였다.

두 개의 정점을 지나야 한다는 것만 해결하면 다익스트라 알고리즘을 이용해 금방 해결할 수 있다.

링크텍스트
백준(1916번)-최소비용 구하기(다익스트라 알고리즘) 링크에 설명해두었으니 참고하면 이해하기에 편할것이다.

import sys
from heapq import heappush, heappop

input = sys.stdin.readline
inf = sys.maxsize
n, e = map(int, input().split())
graph = [[] for _ in range(n + 1)]
dp_1 = [inf] * (n + 1)
dp_2 = [inf] * (n + 1)
dp_3 = [inf] * (n + 1)

def dijkstra(start, dp):
    heap = []
    heappush(heap, [0, start])
    dp[start] = 0
    while heap:
        w, n = heappop(heap)
        for n_n, wei in graph[n]:
            n_w = wei + w
            if n_w < dp[n_n]:
                dp[n_n] = n_w
                heappush(heap, [n_w, n_n])

for _ in range(e):
    a, b, c = map(int, input().split())
    graph[a].append([b, c])
    graph[b].append([a, c])

v1, v2 = map(int, input().split())
dijkstra(1, dp_1)
dijkstra(v1, dp_2)
dijkstra(v2, dp_3)

min_ = min(dp_1[v1] + dp_2[v2] + dp_3[n], dp_1[v2] + dp_2[n] + dp_3[v1])
if min_ >= inf:
    print(-1)
else:
    print(min_)