[Python] 백준 1504 특정한 최단 경로

1504번: 특정한 최단 경로

다익스트라 알고리즘

1 -> N까지 가야하고 v1, v2를 거쳐야 한다. 양뱡향이므로 그래프에 저장할 때 둘 다 저장해야한다. 우선순위 힙을 사용하고 heappush()로 값을 넣고 heappop()으로 값을 추출한다.

 

1) 1에서 출발, v1에서 출발, v2에서 출발하는 세가지 distance를 구한다.

2) 1 -> v1 -> v2 -> N 과 1 -> v2 -> v1 -> N을 비교해서 최솟값이 답이다.

3) 갈 수 없을 때 예외처리

 

전체 코드

import sys
import heapq
import collections
input = sys.stdin.readline

N, E = map(int, input().split())

graph = collections.defaultdict(list)
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())
def dijkstra(start: int):
    distance = [sys.maxsize for _ in range(N+1)]
    distance[start] = 0
    heap = []
    heapq.heappush(heap, (0, start))

    while heap:
        current_distance, current_node = heapq.heappop(heap)
        if distance[current_node] < current_distance:
            continue
        for d, n in graph[current_node]:
            next_distance = d + current_distance
            if next_distance < distance[n]:
                distance[n] = next_distance
                heapq.heappush(heap, (next_distance, n))
    return distance

start_d = dijkstra(1)
v1_d = dijkstra(v1)
v2_d = dijkstra(v2)
fast_d = min(start_d[v1] + v1_d[v2] + v2_d[N], start_d[v2] + v2_d[v1] + v1_d[N])
if fast_d < sys.maxsize:
    print(fast_d)
else:
    print(-1)