[Python] 백준 1054

import heapq
import sys
input = sys.stdin.readline

def dijkstra(start_node):
    queue = []
    min_dist = [1e9] * (n + 1)
    heapq.heappush(queue, [0, start_node])
    min_dist[start_node] = 0
    while queue:
        current_dist, current_node = heapq.heappop(queue)
        for next_node, weight in graph[current_node]:
            cost = min_dist[current_node] + weight
            if cost < min_dist[next_node]:
                min_dist[next_node] = cost
                heapq.heappush(queue, [cost, next_node])

    return min_dist

n,e = map(int, input().split())
graph = [[] for _ in range(n+1)]
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 solve():
    from_1 = dijkstra(1)
    from_v1 = dijkstra(v1)
    from_v2 = dijkstra(v2)

    path1 = from_1[v1] + from_v1[v2] + from_v2[n]
    path2 = from_1[v2] + from_v2[v1] + from_v1[n]

    result = min(path1, path2)

    if result < 1e9:
        return result
    else:
        return -1

print(solve())

 

다익스트라에서 조건문을 추가해서 풀면 되는 쉽고 어려운 문제ㅎㅎ

1 -> v1 -> v2 -> n 까지의 경우와

1 -> v2 -> v1 -> n 까지 경우 중에서 최소비용을 구하면 된다.