문제
https://www.acmicpc.net/problem/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)
'문제풀이 > 최단경로' 카테고리의 다른 글
[파이썬] [최단경로] 백준 14938 서강그라운드 (0) | 2022.03.16 |
---|---|
[파이썬] [최단경로] 백준 1956 운동 (0) | 2022.02.26 |
[파이썬] [최단경로] 백준 11657 타임머신 (0) | 2022.02.09 |
[파이썬] [최단경로] 벨먼포드 (0) | 2022.02.09 |
[파이썬] [최단경로] 백준 18223 민준 (0) | 2022.02.06 |