BOJ 1504번: 특정한 최단 경로

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

1504번: 특정한 최단 경로

 

다익스트라 알고리즘을 이용하여 풀 수 있는 문제였다.

v1, v2를 지나야 하므로 가능한 경로는 두 가지 이다.

1 -> v1 -> v2 -> N

1 -> v2 -> v1 -> N

따라서 시작점을 1, v1, v2로 다익스트라를 실행하여 각각의 경우에 맞는 값을 구한 뒤 더하여 더 짧은 거리를 출력하면 된다. 경로가 없는 경우에 -1을 출력해야 한다는 것도 잊지 말아야 한다.

import sys, heapq
input = sys.stdin.readline
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 solve(start, end):
    ans = [float('INF')]*(N+1)
    ans[start] = 0
    h = []
    heapq.heappush(h, [ans[start], start])
    
    while(h):
        d, u = heapq.heappop(h)
        if ans[u] < d:
            continue #이미 방분한 경우
        for v, c in graph[u]:
            dist = d + c
            if (dist < ans[v]):
                ans[v] = dist
                heapq.heappush(h, [dist, v])
    return ans[end]
    
p1 = solve(1,v1) + solve(v1,v2) + solve(v2,N)
p2 = solve(1,v2) + solve(v2,v1) + solve(v1,N)
if (p1>=float('INF') and p2>=float('INF')):
    print(-1)
else: print(min(p1,p2))