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

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

1504번: 특정한 최단 경로

# 다익스트라 문제이다.

# 기본적인 다익스트라 문제에서 특정한 경로 v1과 v2 정점을 무조건 지나가야 한다는 조건이 붙었다.

 

# 1번 정점부터 N번 정점까지 가는데 있어서 v1, v2정점을 지나는 경우는 2가지 존재한다.

   A. 1번 -> v1 -> v2 -> N번

   B. 1번 -> v2 -> v1 -> N번

 

# 다익스트라를 3번 돌려서 (1번 정점부터 다른 정점까지의 거리, v1 정점부터 다른 정점까지의 거리,

   v2 정점부터 다른 정점까지의 거리) A와 B중 최솟값을 출력하면 된다.

 

import heapq, sys
input = sys.stdin.readline

def dijkstra(start):
    res = [float('INF') for _ in range(V)]
    res[start] = 0
    q = []
    heapq.heappush(q, (res[start], start))
    while q:
        result_x, x = heapq.heappop(q)
        for fu, fw in graph[x]:
            if res[fu] > result_x + fw:
                res[fu] = result_x + fw
                heapq.heappush(q, ([res[fu], fu]))
    return res

V, E = map(int,input().split())
graph = [[] for _ in range(V)]
for _ in range(E):
    u, v, w = map(int,input().split())
    graph[u-1].append((v-1, w))
    graph[v-1].append((u-1, w))
v1, v2 = map(int,input().split())

# 1번 -> N번 정점 경우의 수: 1 -> v1 -> v2 -> N  /  1 -> v2 -> v1 -> N
ans = dijkstra(0)
dv1 = dijkstra(v1-1)
dv2 = dijkstra(v2-1)
dab = min(ans[v1-1] + dv1[v2-1] + dv2[V-1], ans[v2-1] + dv2[v1-1] + dv1[V-1])
print(-1) if dab == float('inf') else print(dab)

(solved.ac 티어: 골드 4)