[1504] 특정한 최단 경로

문제

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

풀이

갈 수 있는 경로는 두 가지가 있습니다.

1. 시작 지점 → v1 → v2 → 종료 지점
2. 시작 지점 → v2 → v1 → 종료 지점

이 두 가지 경우에서 가장 짧은 경로를 구하면 됩니다.

import sys
import heapq

N, E = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N + 1)]
for _ in range(E):
    s, e, d = map(int, sys.stdin.readline().split())
    graph[s].append((e, d))
    graph[e].append((s, d))
target_a, target_b = map(int, sys.stdin.readline().split())

def find_shortest_distance(start, end):
    heap = [(0, start)]
    visited = set()
    while heap:
        total, current_node = heapq.heappop(heap)
        if current_node == end:
            return total
        visited.add(current_node)
        for node, distance in graph[current_node]:
            if node in visited:
                continue
            heapq.heappush(heap, (distance + total, node))
    return -1

start_to_a = find_shortest_distance(1, target_a)
start_to_b = find_shortest_distance(1, target_b)
a_to_b = find_shortest_distance(target_a, target_b)
a_to_end = find_shortest_distance(target_a, N)
b_to_end = find_shortest_distance(target_b, N)
result = -1
if start_to_a != -1 and a_to_b != -1 and b_to_end != -1:
    result = start_to_a + a_to_b + b_to_end

if start_to_b != -1 and a_to_b != -1 and a_to_end != -1:
    result = min(result, start_to_b + a_to_b + a_to_end)
print(result)