문제

문제 링크 : https://www.acmicpc.net/problem/1504

풀이

다익스트라 알고리즘을 사용해서 푸는 문제이다.

하지만 평범한 다익스트라 문제와 다른 점은 "1번 정점에서 N번 정점으로 이동할 때, v1과 v2 정점을 반드시 거치면서 이동하는 최단 경로"를 찾아야 한다는 것이다.

1번 정점에서 N번 정점까지 v1번 정점과 v2번 정점을 반드시 거치면서 이동하는 경우는 크게 두 가지로 나눌 수 있다. 1 -> v1 -> v2 -> N 과 같이 이동하거나 1 -> v2 -> v1 -> N 과 같이 이동하는 경우이다.

따라서 1,v1,v2를 각각 시작점으로 놓고 다익스트라 알고리즘을 사용해서 거리 리스트를 구한다. 구한 리스트를 이용해서 위의 두 경우를 구해서 둘 중 작은 값을 출력한다.

이때 경로가 없는 경우엔 -1을 출력하라고 했으므로 구한 값이 INF 값 이상이라면 -1을 출력한다.

import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)

n,e = map(int,input().split())
graph = [[] for i 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))

def dijkstra(start,n):
    distance = [INF for i in range(n + 1)]
    q = []
    heapq.heappush(q,(0,start))
    distance[start] = 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]))
    return distance

v1, v2 = map(int,input().split())
start_ = dijkstra(1,n)
v1_ = dijkstra(v1,n)
v2_ = dijkstra(v2,n)

result = min(start_[v1] + v1_[v2] + v2_[n], start_[v2] + v2_[v1] + v1_[n])

print(result if result < INF else -1)