문제

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

입력 예시 1

4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3

출력 예시 1

7

문제 이해

다익스트라 알고리즘 유형의 문제인데, 반드시 거쳐가야 하는 점이 2개 주어진다. 다익스트라는 한점을 기준으로 모든 노드에 대한 최단거리를 구하는 알고리즘이다. 우리가 얻어야 할 값은 1을 시작으로 v1이나 v2를 순서 상관없이 거쳐서 N에 도달해야한다. 다익스트라로 풀기 위해서는 1을 기준으로 다익스트라를 돌리고, v1을 기준으로 돌리고, v2를 기준으로 돌린 distance리스트 값을 따로 저장한다. 단순하게 다익스트라 알고리즘을 세 번 돌리면 문제를 해결할 수 있다.

1번을 시작점으로 돌린 리스트 값은 distance_1
v1을 시작점으로 돌린 리스트 값은 distance_v1
v2를 기준으로 돌린 리스트의 값은 distance_v2

경우는 두가지로 나올 수 있다.
CASE1: 1 -> v1 -> v2 -> N
CASE2: 1 -> v2 -> v1 -> N

두 가지로 나오는 이유는 v1에서 v2를 거쳐서 가는게 가까운지, v2에서 v1을 거쳐서 가는 게 더 최단거리인지는 모르기 때문이다. 그래서 이 두 값을 구해서 min()함수로 더 작은 값을 출력할거다. 둘 중에 더 작은 값이 최단거리이기 때문.

각 리스트를 기준으로 노드 A에서 B로 가는 최단거리는 distance_A[B]이다

Example)
1번을 시작점으로 v1으로 가는 최단거리는 distance_1[v1]
v1을 시작점으로 v2로 가는 최단거리는 distance_v1[v2]

그렇다면 CASE 1, 2는 아래와 같다.

# CASE1:  1 -> v1 -> v2 -> N
# CASE2:  1 -> v2 -> v1 -> N 
case1 = distance_1[v1] + distance_v1[v2] + distance_v2[N]
case2 = distance_1[v2] + distance_v2[v1] + distance_v1[N]

코드

# 백준 1504번 특정한 최단 경로

# 읽는 속도 효율화
import sys
input = sys.stdin.readline

# 힙 모듈 import
from queue import PriorityQueue

# function Dijkstra
# 여러번 다익스트라 알고리즘을 이용할 거라서 함수로 구현현
def Dijkstra(start_node):

    distance = [INF] * (N+1)

    pq = PriorityQueue()
    pq.put([0, start_node])
    distance[start_node] = 0

    while not pq.empty():
        cur_distance, cur_node = pq.get()
        
        for adj_node, adj_distance in graph[cur_node]:
            temp_distance = cur_distance + adj_distance
            if temp_distance < distance[adj_node]:
                distance[adj_node] = temp_distance
                pq.put([temp_distance, adj_node])

    return distance

# distance 초기값으로 넣어줄 INF 선언언
INF = int(1e12)

# 0. 입력 및 초기화
N, E = map(int, input().split()) #N노드 E엣지
graph = [[] for _ in range(N+1)]


# 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())

distance_1 = Dijkstra(1) # 1번 노드를 시작점으로 거리값
distance_v1 = Dijkstra(v1) # v1 노드를 시작점으로 거리값
distance_v2 = Dijkstra(v2) # v2 노드를 시작점으로 거리값

# CASE1:  1 -> v1 -> v2 -> N
# CASE2:  1 -> v2 -> v1 -> N 
case1 = distance_1[v1] + distance_v1[v2] + distance_v2[N]
case2 = distance_1[v2] + distance_v2[v1] + distance_v1[N]

# Print result
min_value = min(case1, case2)
print(min_value if min_value < INF else -1)