[백준] 1504번 특정한 최단 경로 [Python] - 데이크스트라

무방향 그래프에 1번에서 u, v 노드를 거쳐서 N번 노드로 가는 최단 경로의 길이를 구하는 문제

1-u-v-N, 1-v-u-N 의 규칙만 지켜서 최단 경로를 구하면 된다.

불가능 할 때, -1을 출력한다.

 

문제

방향성이 없는 그래프가 주어진다. 세준이는 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을 출력한다.

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

 

다익스트라 알고리즘을 사용해서

u에서 1, v, N으로 가는 최단 경로의 길이를 구하고,

v에서 1, N으로 가는 최단 경로 길이를 구한다.

$($v에서 u로 가는 최단 경로의 길이는 u에서 v로 가는 최단 경로의 길이와 같다.$)$

 

$($a-b: a와 b사이의 최단 경로의 길이$)$

1-u + v-N 과 1-v + u+N 중에 최솟값에 u-v를 더한 값을 출력한다.

 

import sys
from heapq import heappop, heappush
input = sys.stdin.readline

def main():
    INF = float('inf')
    N, E = map(int, input().split())
    graph = {n: {} for n in range(1, N+1)}

    for _ in range(E):
        a, b, c = map(int, input().split())
        graph[a][b] = c
        graph[b][a] = c

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

    def f(node, li):
        dist = [INF]*(N+1)
        dist[node] = 0
        q = [(0, node)]
        while q:
            d0, s = heappop(q)
            if d0 > dist[s]:
                continue
            for e, d1 in graph[s].items():
                if (d:= d0 + d1) < dist[e]:
                    dist[e] = d
                    heappush(q, (d, e))
        return [dist[i] for i in li]
    
    d1, d2 = f(v1, [1, N, v2]), f(v2, [N, 1])
    ans = min([x+y for x, y in zip(d1, d2)]) + d1[2]
    print(ans if ans != INF else '-1')

if __name__ == "__main__":
    main()

 

 

예제 입력 1 

4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3

예제 출력 1 

7