[백준/Python] #1504 특정한 최단 경

문제

 

https://www.acmicpc.net/submit/1504/61065431

로그인

---

Algorithm

다익스트라 알고리즘을 이용한다. 시작점이 정점 1인 경우에서 다익스트라 알고리즘을 수행했을 때와 시작점이 각각 정점 v_1, v_2인 경우에서 다익스트라 알고리즘을 수행했을 때의 결괏값 3개를 구한다. 이 결괏값을 각각 d_0, d_1, d_2이라 하면 이 결괏값들은 모두 리스트이다. 경로가 "정점 1->정점 v_1->정점 v_2->정점 N"일 때와 "정점 1->정점 v_2->정점 v_1->정점 N"일 때 중에서 길이가 더 짧은 경로의 길이를 출력한다. 다시 말해 d_{k-1}의 i번째 원소는(1<=k<=N, 1<=i<=N) 출발점이 정점 k일 때 정점 i까지의 최소 경로의 길이를 의미하므로 d_0[v_1]+d_3[v_2]+d_1[N]와 d_0[v_2]+d_2[v_1]+d_1[N] 중에서 저 작은 값을 출력한다. 이 때 이 두 개의 값이 모두 float("inf")이면 문제에서 요구하는 경로가 없다는 의미이므로 -1을 출력한다.

 

---

 

 

Code

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

def dijkdtra(s):
    queue = []
    distance = [float("inf") for _ in range(N + 1)]
    heappush(queue, (0, s))
    distance[s] = 0
    while queue:
        ud, uc = heappop(queue)
        if distance[uc] < ud:
            continue
        for (d, c) in nodes[uc]:
            cd = d + ud
            if distance[c] >= cd:
                distance[c] = cd
                heappush(queue, (cd, c))
    return distance

N, E = map(int, input().split())

nodes = [[] for _ in range(N + 1)]
for i in range(E):
    a, b, c = map(int, input().split())
    nodes[a].append((c, b))
    nodes[b].append((c, a))

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

d0 = dijkdtra(1)
d1 = dijkdtra(v1)
d2 = dijkdtra(v2)

case1 = d0[v1] + d1[v2] + d2[N]
case2 = d0[v2] + d2[v1] + d1[N]
minPath = min(case1, case2)
if minPath != float("inf"):
    print(minPath)
else:
    print(-1)