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

문제

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

풀이

시작점 -> 지점 1 -> 지점 2 -> 도착점
시작점 -> 지점 2 -> 지점 1 -> 도착점

의 거리를 구해서 작은 값을 구한다.
만약 두 결과값 모두 최대값보다 큰 값이 이라면 도달할 수 없는 지점이므로
-1 을 출력한다.

최대 값보다 큰 값이 나올 수 있는 이유는 부분적으로 다익스트라를 돌리고 결과값을 더하기 때문이다.

Ex)
시작점 -> 지점 1 = 6
지점 1 -> 지점 2 = INF
지점 2 -> 도착점 = 3
결과: 6 +INF + 3

import sys
import heapq

sys.stdin = open('data.txt', 'r')

INF = sys.maxsize
N, E = map(int, input().rstrip().split(" "))
graph = {vertex: {} for vertex in range(1, N + 1)}
for _ in range(E):
    start, end, distance = map(int, input().rstrip().split(" "))
    if end not in graph[start]:
        graph[start][end] = distance
    else:
        graph[start][end] = min(graph[start][end], distance)

    if start not in graph[end]:
        graph[end][start] = distance
    else:
        graph[end][start] = min(graph[end][start], distance)

target1, target2 = map(int, input().rstrip().split(" "))


def dijkstra(start, end, graph, N):
    distances = [INF] * (N + 1)
    heap = [(0, start)]
    distances[start] = 0

    while heap:
        cur_distance, cur = heapq.heappop(heap)

        if distances[cur] < cur_distance:
            continue

        for neighbor, weight in graph[cur].items():
            next_distance = cur_distance + weight

            if next_distance < distances[neighbor]:
                distances[neighbor] = next_distance
                heapq.heappush(heap, (next_distance, neighbor))

    return distances[end]


def solution(N, E, graph, target1, target2):
    answer1 = dijkstra(1, target1, graph, N) + dijkstra(target1, target2, graph, N) + dijkstra(target2, N, graph, N)
    answer2 = dijkstra(1, target2, graph, N) + dijkstra(target2, target1, graph, N) + dijkstra(target1, N, graph, N)

    result = min(answer1, answer2)
    print(result if result < INF else -1)
    return


solution(N, E, graph, target1, target2)