백준 1504: 특정한 최단 경로 - 다익스트라(Python/파이썬)

1. 첫 제출
   다익스트라를 썼는데 다익스트라는 한 노드에서 다른 노드까지의 최단 거리를 구하는 것이지 그 사이에 몇 개의 노드를 거쳤는가는 파악이 안 되기 때문에 틀렸다. 오류 코드
   

2. 수정(다익스트라 3번)

• 시작점에서 출발하는 다익스트라
• v1에서 출발하는 다익스트라
• v2에서 출발하는 다익스트라

각각 구해서 (출발점 -> v1 -> v2 -> 도착점)과 (출발점 -> v2 -> v1 -> 출발점) 중 최솟값 출력

import sys
import heapq

input = sys.stdin.readline

def dijkstra(start):
    visited = [float('inf')] * (N+1)
    q = []
    heapq.heappush(q, (0, start))
    visited[start] = 0

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

        for node in graph[now]:
            sum_cost = cost + node[0]
            if visited[node[1]] > sum_cost:
                visited[node[1]] = sum_cost
                heapq.heappush(q, (sum_cost, node[1]))

    return visited


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((c, b))
    graph[b].append((c, a))

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

cost_start = dijkstra(1)
cost_v1 = dijkstra(v1)
cost_v2 = dijkstra(v2)

res1 = cost_start[v1] + cost_v1[v2] + cost_v2[N] # 1->v1->v2->N
res2 = cost_start[v2] + cost_v2[v1] + cost_v1[N] # 1->v2->v1->N

if res1 < float('inf') and res2 < float('inf'):
    print(min(res1, res2))
else:
    print(-1)