[최단 경로] 백준 1504번: 특정한 최단 경로 / 골드 4

https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존

www.acmicpc.net

import collections
import heapq
import sys
n, e = map(int, input().split())
graph = collections.defaultdict(list)
for i in range(e):
    u,v,w = map(int, input().split())
    graph[u].append([v,w])
    graph[v].append([u,w])

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

def dijkstra(start, end):
    start = [0, start]  # cost, node
    dist = {}
    q = []
    heapq.heappush(q, start)
    while q:
        cost, node = heapq.heappop(q)
        if node not in dist:
            dist[node] = cost
            if node == end:
                break
            for next, w in graph[node]:
                heapq.heappush(q, [w+cost, next])
    if end in dist:
        return dist[end]
    else:
        return -sys.maxsize

answer = dijkstra(1,v1) + dijkstra(v1,v2) + dijkstra(v2,n)
answer2 = dijkstra(1,v2) + dijkstra(v2,v1) + dijkstra(v1,n)
if answer < 0 and answer2 < 0:
    print(-1)
elif answer < 0:
    print(answer2)
elif answer2 < 0:
    print(answer)
else:
    print(min(answer, answer2))

v1과 v2를 반드시 거쳐야 한다.

start -> v1 -> v2 -> end

start -> v2 -> v1 -> end

둘 다 해봐서 작은 값을 출력하도록 하였다.

이게 가장 효율적이진 않은 거 같은데...