[백준] 1504- 특정한 최단 경로 (Python)

문제

---

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

예제 출력 1

---

7

해결 방법

최단 경로의 길이를 구하는 문제이지만 특정한 노드를 반드시 거쳐야 한다는 제약조건이 있다. 

시작 지점을 Start, 종점을 End, 거쳐야 할 노드를 V1, V2라고 한다면

고려해 볼 수 있는 경우의 수는 

1. Start - V1 - V2 - End

2. Start - V2 - V1 - End 로 볼 수 있다. 

 

Start - V1 - V2 - End 혹은 Start - V2 - V1 - End  가 최단 경로가 되기 위해서는

Start - V1 , V1 - V2, V2 -  End가 각각 최단 경로 만족시키거나 혹은

Start - V2, V2 - V1, V1 - End가 각각 최단 경로를 만족시켜야 한다. 

 

이를 구현하기 위해 

Start 에서 각 노드에 대한 최단 경로

V1 에서 각 노드에 대한 최단 경로

V2 에서 각 노드에 대한 최단 경로를 각각 구한 뒤, 

Start - V1 - V2 - End 와 Start - V2 - V1 - End 중에서 최솟값을 가지는 값을 선택하면 된다. 

import sys
import heapq
import copy 

INF = int(1e9)

n,m = map(int,input().split())

graph = [[] for _ in range(n+1)]

for _ in range(m):
    a,b,c = map(int,sys.stdin.readline().split())
    graph[a].append((c,b))
    graph[b].append((c,a))

x,y = map(int,input().split())

queue = []
def dijkstra(start):
    heapq.heappush(queue, (0, start))
    distance[start] = 0
    while queue:
        dist, current = heapq.heappop(queue)
        if distance[current] < dist:
            continue
        for node in graph[current]:
            cost = dist + node[0]
            if distance[node[1]] > cost:
                distance[node[1]] = cost
                heapq.heappush(queue, (cost, node[1]))

distance = [INF] * (n+1)
dijkstra(1)
ds = copy.deepcopy(distance)

distance = [INF] * (n+1)
dijkstra(x)
dx = copy.deepcopy(distance)

distance = [INF] * (n+1)
dijkstra(y)
dy = copy.deepcopy(distance)


print(-1 if min(ds[x] + dx[y] + dy[n], ds[y] + dy[x] + dx[n]) >= INF else min(ds[x] + dx[y] + dy[n], ds[y] + dy[x] + dx[n]))