다익스트라 - 1504번: 특정한 최단 경로

• 경로는 1→V1→V2→N, 1→V2→V1→N 두 가지 경우만 고려하면 됨!
• 다익스트라는 dijkstra(1), dijkstra(V1), dijkstra(V2) 총 3번만 돌리면 구할 수 있음

from collections import defaultdict
import heapq

N, E = map(int, input().split())
graph = defaultdict(list)

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


V1, V2 = map(int, input().split())


def dijkstra(start):
    dist = [float("inf")] * (N + 1)
    dist[start] = 0

    heap = []
    heapq.heappush(heap, (0, start))

    while heap:
        cost, node = heapq.heappop(heap)

        if dist[node] < cost:
            continue

        for v, w in graph[node]:
            new_cost = cost + w

            if new_cost < dist[v]:
                dist[v] = new_cost
                heapq.heappush(heap, (new_cost, v))

    return dist


dist_1 = dijkstra(1)

dist_V1 = dijkstra(V1)

dist_V2 = dijkstra(V2)

# 경우 1) 1 -> V1 -> V2 -> N 최단경로
total_dist_1 = dist_1[V1] + dist_V1[V2] + dist_V2[N]
# 경우 2) 1 -> V2 -> V1 -> N 최단경로
total_dist_2 = dist_1[V2] + dist_V2[V1] + dist_V1[N]

# 두 경우 중 더 최단경로 선택
answer = min(total_dist_1, total_dist_2)


# 만약 경로가 아예 존재하지 않는다면 -1 출력 (더한 경로들 중 하나라도 경로가 없어서 무한대가 더해졌다면 total 값은 무한대일 것이므로)
if answer == float("inf"):
    print(-1)
else:
    print(answer)