백준 1504 - 특정한 최단경로 (파이썬)

Answer

from sys import stdin
from heapq import heappush, heappop

input = stdin.readline

INF = float('inf')
N, E = map(int, input().split())
graph = [[] for _ in range(N + 1)]

def dijkstra(start):
    dp = [INF] * (N + 1)
    dp[start] = 0
    heap = [(0, start)]

    while heap:
        weight, current = heappop(heap)

        if dp[current] < weight:
            continue

        for w, next in graph[current]:
            next_weight = weight + w

            if next_weight < dp[next]:
                dp[next] = next_weight
                heappush(heap, (next_weight, next))

    return dp

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

v1, v2 = map(int, input().split())

start_dp = dijkstra(1)
v1_dp = dijkstra(v1)
v2_dp = dijkstra(v2)

path1 = start_dp[v1] + v1_dp[v2] + v2_dp[N]
path2 = start_dp[v2] + v2_dp[v1] + v1_dp[N]
answer = min(path1, path2)
 
print(answer if answer < INF else -1)