문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

# 1504
import sys
input = lambda : sys.stdin.readline().strip()
INF = int(1e9)

import heapq
n, e = map(int, input().split())
graph = [[] for _ in range(n+1)]
distance = [INF] * (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 = map(int, input().split())
    
# start = 1, end = n
# v1, v2 : 반드시 통과해야 함
# start > v1 > v2 > end
# start > v2 > v1 > end
# start > v1 > v2 > v1 > end
# start > v2 > v1 > v2 > end

# 필요한 정보
# start > v1 : in_s1
# start > v2 : in_s2
# v1 > v2 : in_12
# v1 > end : in_1e
# v2 > end : in_2e

def dijkstra(node):
    q = []
    heapq.heappush(q, (0, node))
    distance[node] = 0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))


# 필요 정보 : in_s1, in_s2
dijkstra(1)
in_s1 = distance[v1]
in_s2 = distance[v2]
distance = [INF] * (n+1)

# 필요 정보 : in_12, in_1e
dijkstra(v1)
in_12 = distance[v2]
in_1e = distance[n]
distance = [INF] * (n+1)

# 필요 정보 : in_2e
dijkstra(v2)
in_2e = distance[n]

my_dist = []
# start > v1 > v2 > end
my_dist.append(in_s1 + in_12 + in_2e)
# start > v2 > v1 > end
my_dist.append(in_s2 + in_12 + in_1e)
# start > v1 > v2 > v1 > end
my_dist.append(in_s1 + in_12 + in_12 + in_1e)
# start > v2 > v1 > v2 > end
my_dist.append(in_s2 + in_12 + in_12 + in_2e)

less_dist = min(my_dist)
if less_dist >= INF:
    print("-1")
else:
    print(less_dist)

백준 1504 특정한 최단 경로