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

문제

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

1504번: 특정한 최단 경로

 

코드

import heapq
import sys
input=sys.stdin.readline
INF=sys.maxsize

def dijk(start):
    dis = [INF] * (n + 1)
    q=[]
    heapq.heappush(q,(0,start))
    dis[start]=0

    while q:
        cost,node=heapq.heappop(q)
        if dis[node]<cost:
            continue
        for i in graph[node]:
            new_cost=cost+i[1]
            if new_cost<dis[i[0]]:
                dis[i[0]]=new_cost
                heapq.heappush(q,(new_cost,i[0]))
    return dis


n,m=map(int, input().split())
graph=[[] for _ in range(n+1)]

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


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

one=dijk(1)
v1_=dijk(v1)
v2_=dijk(v2)

result=min(one[v1]+v1_[v2]+v2_[n],one[v2]+v2_[v1]+v1_[n])
if result<INF:
    print(result)
else:
    print(-1)