BOJ 1504 특정한 최단 경로

https://www.acmicpc.net/problem/1504
시간 1초, 메모리 256MB
input :

• N E(2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000)
• a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000)
• 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1)

output :

• 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력

조건 :

• 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램

---

1번 에서 N 까지 이동을 하는데 두 점을 거치는 방법은?
1 - v1 - v2 - n
1 - v2 - v1 - n
두 가지 경우 밖에 존재 하지 않는다.

그렇기 때문에 1 에서 최단 경로를 구하고,
v1 에서의 최단경로, v2에서의 최단 경로를 모두 구한 다음에.
경로들의 거리를 비교해서 더 짧은 것을 출력한다.

import sys
import heapq

n, e = map(int, sys.stdin.readline().split())
graph = [[] for i in range(n + 1)]
for i in range(e):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append((b, c))
    graph[b].append((a, c))
v1, v2 = map(int, sys.stdin.readline().split())

def dijkstra(start):
    ret = [999999] * (n + 1)
    ret[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        cost, now = heapq.heappop(q)

        if cost > ret[now]:
            continue

        for next_node, next_cost in graph[now]:

            total_cost = next_cost + cost

            if ret[next_node] > total_cost:
                ret[next_node] = total_cost
                heapq.heappush(q, (total_cost, next_node))
    return ret

one = dijkstra(1)
list_v1 = dijkstra(v1)
list_v2 = dijkstra(v2)
ret = min(one[v1] + list_v1[v2] + list_v2[n], one[v2] + list_v2[v1] + list_v1[n])
if ret < 999999:
    print(ret)
else:
    print(-1)

오늘은 heap을 한 번 더 봐야 겠다