두 단계 최단 경로1(백준 23793)

파이썬의 heapq를 사용하고 다익스트라 알고리즘을 사용했다. 

 

inf로 정의된 수가 무한대가 아니기 때문에 중간 경유지를 거치고 종착지에 도달한 거리가 inf보다도 길 수가 있다는 점을 주의해야 한다. 

import heapq 
import sys 
input = sys.stdin.readline 
inf = int(2e9)
n,m = map(int, input().split())
gra = [[]for i in range(n+1)]

for i in range(m):
    a,b,c = map(int, input().split())
    gra[a].append((b,c))
start,middle,end = map(int, input().split())
# print(gra)


def dijk(start,middle , end):
    
    dist = [inf]*(n+1)
    dist[start] = 0 
    q = []
    q.append((0,start))
    heapq.heapify(q)
    # heapq.heappush(q, (0,start))
    while q:
        wei,x = heapq.heappop(q)
        if( wei > dist[x]):
            continue 
        for nextx, cost in (gra[x]):
            if(nextx ==middle and ((start != middle) and (middle !=end))):
                continue
            # nextx,cost =gra[x][i] 
            if(dist[nextx] > wei+ cost ):
                dist[nextx] = wei+cost 
                heapq.heappush(q, (wei+cost, nextx))
                
    return dist[end] 
    
                
        
ans1 , ans2 = dijk(start,middle, middle)+ dijk(middle, middle, end),dijk(start, middle , end )
# print(dijk(start,middle, middle)+ dijk(middle, middle, end))
# print(dijk(start, middle , end ))
if(ans1 >= inf):
    ans1 = -1 
if(ans2 >=inf):
    ans2 = -1 
print(ans1, ans2)