[ BOJ 1504 ] 특정한 최단 경로(Python)

문제

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

1번 정점에서 n번 정점으로 이동할 때, 임의로 주어진 두 정점을 반드시 통과해서 지나야 한다.

• 이때 최단 경로로 갈 수 있다면 한번 이동했던 정점이나 간선을 다시 이용해도 된다.

문제 풀이

1번 정점에서 n번 정점으로 이동할 때, 거쳐야 하는 두 정점 v1, v2의 경우를 따로 비교해야 한다.
이 문제를 풀려면 이 생각을 먼저 떠올려야 하는 것 같다. 💭

[1] 1번 ➣ v1 ➣ v2 ➣ n번
1번이 출발지이고, v1이 도착지일때 가장 짧은 경로 + v1이 출발지이고, v2가 도착지일때 가장 짧은 경로 + v2가 출발지이고, n번이 도착지일때 가장 짧은 경로

[2] 1번 ➣ v2 ➣ v1 ➣ n번
1번이 출발지이고, v2가 도착지일때 가장 짧은 경로 + v2가 출발지이고, v1이 도착지일때 가장 짧은 경로 + v1이 출발지이고, n번이 도착지일때 가장 짧은 경로

두 정점을 거칠 때, 위와 같은 경우로 나누어서 더 짧은 경로를 선택해서 출력해주면 된다.

1. 방향 없는 그래프이므로 양방향으로 이어주기
2. [1], [2] 경우 중 더 작은 값을 answer 변수에 저장하기
   2-1. 만약 answer가 MAX_INT 값보다 크면 이동할 수 없는 경로이므로 -1을 리턴해준다.

코드

import sys
import heapq

input = sys.stdin.readline
MAX_INT = sys.maxsize

def dijkstra(start):
    distance = [MAX_INT for _ in range(n+1)]
    q = [start] # [비용,시작점]
    
    # 자기 자신의 거리 0으로 만들기
    distance[start[1]] = 0
    while q:
        p = heapq.heappop(q)
        cur_cost, cur_location = p[0], p[1]
        # 현재 위치한 정점과 연결된 정점 Next 들 방문
        for next_cost, next_location in graph[cur_location]:
            # (연결된 정점으로 이동 비용) vs (현재 비용 + 이동 비용): 더 작은 값으로 할당 해줌
            if distance[next_location] > cur_cost + next_cost:
                distance[next_location] = cur_cost + next_cost
                heapq.heappush(q,[distance[next_location],next_location])
    return distance

n,e = map(int,input().rstrip().rsplit())
graph = [[] for _ in range(n+1)] 
for _ in range(e):
    a, b, c = map(int,input().rstrip().rsplit())
    # graph[출발지] = [비용,도착지]
    graph[a].append([c,b])
    graph[b].append([c,a])
    
# 경유지 v1, v2 
v1, v2 = map(int,input().rstrip().rsplit())

go = dijkstra([0,1])
v1go = dijkstra([0,v1])
v2go = dijkstra([0,v2])

answer = (min(go[v1]+v1go[v2]+v2go[n],go[v2]+v2go[v1]+v1go[n]))
if answer >= MAX_INT:
    print(-1)
else:
    print(answer)