알고리즘/백준
[백준] 1504번 특정한 최단 경로 (파이썬)
알감자
2022. 1. 5. 23:15
1504번: 특정한 최단 경로
첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존
www.acmicpc.net
코드
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)