# 1504 특정한 최단 경로

www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

import heapq
import sys
input = sys.stdin.readline

n, e = map(int,input().split()) # 정점, 간선 

graph=[ [] for _ 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))

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

def dij(start):
  q = [] 
  heapq.heappush(q,(0,start))
  dist = [1e9]*(n+1)
  dist[start]=0 

  while q:
    d, now = heapq.heappop(q)
    if dist[now] < d : continue 

    for i in graph[now]:
      cost = d + i[1]
      if cost < dist[i[0]]:
        dist[i[0]] = cost 
        heapq.heappush(q, (cost,i[0]))
  return dist 


dist_1 = dij(1)
dist_v1 = dij(v1)
dist_v2 = dij(v2)

answer = min( dist_1[v1]+dist_v1[v2]+dist_v2[n], 
  dist_1[v2]+ dist_v2[v1]+dist_v1[n])

if answer >= 1e9 : 
  print(-1)
else : 
  print(answer)

 

주의사항 ) 

 

1. 양방향 그래프 => graph 에 추가할 때 앞 뒤로 다 해주기 

2. v1, v2 는 지나는 순서가 정해진 것은 x => 경우의 수 2개로 나누어서 더 작은 것으로 선택하기