[백준] 1504번 특정한 최단 경로 (파이썬)

1504번: 특정한 최단 경로

 

코드

import heapq
import sys

n, e = map(int, input().split())

inf = sys.maxsize
heap = []
tree = list([] for _ in range(n+1))


def dijkstra(start):
    destination = [inf] * (n + 1)
    destination[start] = 0
    heapq.heappush(heap, [destination[start], start])
    while heap:
        w, v = heapq.heappop(heap)
        for node, distance in tree[v]:
            new_distance = w + distance
            if new_distance < destination[node]:
                destination[node] = new_distance
                heapq.heappush(heap, [new_distance, node])
    return destination

for _ in range(e):
    x, y, z = map(int,input().split())
    tree[x].append([y,z])
    tree[y].append([x,z])

v1, v2 = map(int, input().split())
one = dijkstra(1)
v1_ = dijkstra(v1)
v2_ = dijkstra(v2)
cnt = min(one[v1] + v1_[v2] + v2_[n], one[v2] + v2_[v1] + v1_[n])
print(cnt if cnt < inf else -1)