코드

import sys
import heapq

INF = int(10**9)

input = sys.stdin.readline


V,E = map(int,input().split(" "))   

graph = [[] for _ in range(V+1)]

for i in range(E):
    a,b,w = map(int,input().split(" "))
    graph[a].append((b,w))
    graph[b].append((a,w))

v1,v2 = map(int,input().split(" "))

def dijkstra(start):
    distance = [INF] * (V+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 distance[i[0]] > cost:
                distance[i[0]] = cost
                heapq.heappush(q,(cost,i[0]))

    
    return distance





og_distance = dijkstra(1)
v1_distance = dijkstra(v1)
v2_distance = dijkstra(v2)


v1_path = og_distance[v1] + v1_distance[v2] + v2_distance[V] #1->v1, v1->v2, v2->V
v2_path = og_distance[v2] + v2_distance[v1] + v1_distance[V] #1->v2, v2->v1, v1->V

result = min(v1_path,v2_path)

print(result if result < INF else -1)

풀이

• 전형적인 다익스트라 문제
  - 한 정점에서 다른 모든 정점으로 가는 최단거리를 구함.
• 1,v1,v2 에서 시작했을 때의 최단거리 리스트를 구함.
• 1->v1->v2->V, 1->v2->v1->V 경로 중 작은 값이 result
• 길이 없다면 INF가 나올 것이므로 그럴 때는 -1 출력