[ 백준 / 파이썬 ] 골드 4 - 1504. 특정한 최단 경로

난이도

문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

예제

입력	출력
4 6 1 2 3 2 3 3 3 4 1 1 3 5 2 4 5 1 4 4 2 3	7

풀이

반드시 두 점을 지나는 최단 거리를 구해야 하므로, 출발점에서 두 점까지의 최단 거리를 구하고, 두 점 서로의 최단 거리를 구하고, 두 점에서 목적지 까지의 최단 거리의 합이 이 문제의 답이다.

즉 다익스트라를 세번 적용하면 문제를 해결할 수 있다.

1. 출발지에서 V1, V2 까지의 최단 거리
2. V1 에서 V2, 목적지 까지의 최단 거리
3. V2 에서 V1, 목적지 까지의 최단 거리

재방문이 가능하다는 점에서 해당 문제가 까다롭게 여겨졌는데, 생각을 다르게 해보니 문제가 풀렸다.

굳이 어렵게 재방문 가능한 상태에서 출발지부터 목적지까지의 최단거리를 찾지 말고,
출발지로 부터 반드시 지나야할 정점까지의 최단거리, 정점부터 목적지 까지의 최단거리의 합이,
곧 중복된 간선이 포함된 모든 간선 중의 최단거리인 셈이다.

코드

from sys import stdin
from heapq import heappush, heappop

input = stdin.readline


def dijkstar(start, graph, distance):
    visited = [False] * len(distance)
    distance[start] = 0
    visited[start] = True

    heap = []
    heappush(heap, (0, start))

    while heap:
        cost, node = heappop(heap)

        if distance[node] < cost:
            continue

        for branch in graph[node]:
            next_cost = cost + branch[0]
            next_node = branch[1]

            if next_cost < distance[next_node] and not visited[next_node]:
                distance[next_node] = next_cost
                heappush(heap, (next_cost, next_node))


def solution():
    N, E = map(int, input().split())
    graph = [[] for _ in range(N + 1)]

    for _ in range(E):
        S, E, C = map(int, input().split())
        graph[S].append((C, E))
        graph[E].append((C, S))

    V1, V2 = map(int, input().split())

    distance_1 =[2e9] * (N+1)
    distance_V1 = [2e9] * (N+1)
    distance_V2 = [2e9] * (N+1)

    dijkstar(1, graph, distance_1)
    dijkstar(V1, graph, distance_V1)
    dijkstar(V2, graph, distance_V2)


    answer = min(distance_1[V1] + distance_V1[V2] + distance_V2[N],
                 distance_1[V2] + distance_V2[V1] + distance_V1[N])
    if answer >= 2e9:
        answer = -1

    return answer

print(solution())