알고리즘: 백준 1504번 특정한 최단 경로 (feat. python)

 

1504번: 특정한 최단 경로

 

 

import sys
import heapq
read = sys.stdin.readline
N, E = map(int, read().split())
graph = {i:[] for i in range(1, N+1)}
for _ in range(E):
    a, b, c = map(int, read().split())
    graph[a].append([b,c])
    graph[b].append([a,c])
v1, v2 = map(int ,read().split())
INF = sys.maxsize

def dijkstra(start, dist):

    dist[start] = 0
    hq = []
    heapq.heappush(hq, [0, start])

    while hq:
        cw, cn = heapq.heappop(hq)
        for nn, nw in graph[cn]:
            next = nw + cw
            if next < dist[nn]:
                dist[nn] = next
                heapq.heappush(hq, [next, nn])

dist = [0] + [INF for _ in range(N)]
dist2 = [0] + [INF for _ in range(N)]
dist3 = [0] + [INF for _ in range(N)]

dijkstra(1, dist)
dijkstra(v1, dist2)
dijkstra(v2, dist3)

if dist[v1] + dist3[N] > dist[v2] + dist2[N] and dist[v2] + dist2[N] + dist2[v2] < INF:
    print(dist[v2] + dist2[N] + dist2[v2])
elif dist[v1] + dist3[N] <= dist[v2] + dist2[N] and dist[v1] + dist3[N] + dist2[v2] < INF:
    print(dist[v1] + dist3[N] + dist2[v2])
else:
    print(-1)