[다익스트라] (백준_1504) 특정한 최단경로 - 파이썬

✅ 특정노드사이의 비용을 최소비용으로 잘못판단했다. => 이부분(start_v1[v2],start_v2[v1]) / 어느 지점을 특히 지나가야한다면 그사이에서도 다른 노드를 지날때가 더 최소일 수도 있다는걸 명심하자

#수정 후
path_1_v1_v2_N = start_1[v1]+start_v1[v2]+start_v2[N]
path_1_v2_v1_N = start_1[v2]+start_v2[v1]+start_v1[N]


#수정 전
v1_v2_cost=INF
for (node, cost) in graph[v1]:
    if node==v2:
        v1_v2_cost=cost
path_1_v1_v2_N = start_1[v1]+v1_v2_cost+start_v2[N]
path_1_v2_v1_N = start_1[v2]+v1_v2_cost+start_v1[N]

 

풀이

import heapq
INF=int(1e9)
N,E = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ 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 dijkstra(start):
    distance = [INF]*(N+1)
    distance[start]=0
    q=[]
    heapq.heappush(q,(0,start))
    while q:
        dist,now = heapq.heappop(q)
        if distance[now]<dist:
            continue
        for next_node, next_cost in graph[now]:
            next_dist = dist+next_cost
            if next_dist<distance[next_node]:
                distance[next_node]=next_dist
                heapq.heappush(q,(next_dist,next_node))
    return distance

start_1=dijkstra(1)
start_v1=dijkstra(v1)
start_v2=dijkstra(v2)

path_1_v1_v2_N = start_1[v1]+start_v1[v2]+start_v2[N]
path_1_v2_v1_N = start_1[v2]+start_v2[v1]+start_v1[N]
result = min(path_1_v1_v2_N,path_1_v2_v1_N)
if result >= INF:
    print(-1)
else:
    print(result)