백준 / 1504 / 특정한 최단 경로 / python

import sys
input = sys.stdin.readline
from heapq import heappop, heappush

def dijkstra(start):
    dist = [1e9] * (n+1)
    dist[start] = 0

    h = []
    heappush(h, (0, start))

    while h:
        dis, node = heappop(h)
        if dist[node] < dis:
            continue

        for next_node, next_dis in graph[node]:
            d = dis + next_dis
            if dist[next_node] > d:
                dist[next_node] = d
                heappush(h, (d, next_node))
    
    return dist

n, e = [int(v) for v in input().split()]
graph = [[] for _ in range(n+1)]

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

v1, v2 = [int(v) for v in input().split()]

origin_d = dijkstra(1)
v1_dijkstra = dijkstra(v1)
v2_dijkstra = dijkstra(v2)

v1_path = origin_d[v1] + v1_dijkstra[v2] + v2_dijkstra[n]
v2_path = origin_d[v2] + v2_dijkstra[v1] + v1_dijkstra[n]

result = min(v1_path, v2_path)
print(result if result < 1e9 else -1)

1번 노드에서 정점노드까지 가는 길에 반드시 주어지는 두 노드를 지나야한다.

반드시 두 노드를 지나게 하는 방법은 시작점의 다익스트라 뿐 아니라 주어진 두 노드를 시작점으로 하는 다익스트라를 각각 구해준 후 두 노드를 지나는 경로를 직접 구해주면 된다.

즉 시작점 -> v1 -> v2 -> 정점, 시작점 -> v2 -> v1 -> 정점 이 두가지 경로를 구해주면 된다.