[Python] 백준 1504번: 특정한 최단 경로

최단 경로를 구하되, 특정 노드 2곳을 꼭 거쳐야 하는 최단 경로를 구하는 문제
문제 링크 https://www.acmicpc.net/problem/1504

• 정점의 개수가 2이상 800이하, 간선의 개수 0이상 200,000이하. 제한 시간 1초
  --> 플루이드 워셜로 구현하면 시간초과. 다익스트라로 구현해야 함

• 시작 노드부터 끝 노드까지의 최단 경로를 각각 구해서 더하는 방법으로 구현

• v1과 v2의 방문 순서에 따라 최단 거리가 달라질 수 있으므로 min()을 이용하여 더 짧은 거리를 선택

• 거리가 1e9일 경우 경로가 없으므로 -1출력. (맞왜틀..^_T)

import sys
import heapq
input = sys.stdin.readline

# N = 노드의 개수 E 간선의 개수
N, E = map(int, input().split())
nodes = [[] for _ in range(N+1)]

# 거리 정보 저장
for info in range(E):
    a, b, c = map(int, input().split())
    nodes[a].append([b,c])  # 양방향
    nodes[b].append([a,c])

def dijkstra(start, end):
    distance = [int(1e9)] * (N+1)
    distance[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        dist, now = heapq.heappop(q)
        if dist > distance[now]:
            continue
        for i in nodes[now]:
            cost = dist+i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost,i[0]))
    return distance[end]
v1, v2 = map(int, input().split())

# 먼저 가는 순서에 따라 최단거리가 달라질 수 있으므로
answer = min(dijkstra(1, v1)+dijkstra(v1,v2)+dijkstra(v2,N), dijkstra(1, v2)+dijkstra(v2,v1)+dijkstra(v1,N))
if answer>=int(1e9):
    print(-1)
else:
    print(answer)