Apple Delivery(백준 5944)

다익스트라 알고리즘을 주어지는 node에 대해서 각각 수행한다. 이후에 방문순서에 따른 거리를 계산해서 최소 거리를 찾는다. 

import sys 
import heapq 
input = sys.stdin.readline 
m,n,s,e1,e2 =map(int, input().split())
inf =int(1e9)
dist  = [inf for _ in range(n+1)]
dist2 = [inf for _ in range(n+1)]
dist3 = [inf for _ in range(n+1)]
gra   = [[] for _ in range(n+1)]
for i in range(m):
    a,b,c= map(int, input().split())
    gra[a].append((b,c))
    gra[b].append((a,c))
    
def dijk(start, dist):
    q =[]
    q.append((0,start))
    dist[start] =0 
    heapq.heapify(q)
    
    while q :
        wei, now =heapq.heappop(q)
        if dist[now] < wei:
            continue 
        for   nextnode,cost in gra[now] :
            if dist[nextnode] > wei+cost :
                dist[nextnode] = wei+cost 
                heapq.heappush(q,(wei+cost, nextnode))
                
        

dijk(s ,dist)
dijk(e1, dist2) 
dijk(e2, dist3) 
ans1 = dist[e1] + dist2[e2]
ans2 = dist[e2] + dist3[e1]
print(min(ans1,ans2))

#2가지 경우를 비교하고 더 작은 것 고르기