백준 GOLD 4 [1504번] 특정한 최단 경로 {언어 : Python}

문제 링크

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

정답 코드

import sys
import heapq

input = sys.stdin.readline
n, e = map(int, input().split())
adjL = [[] for _ in range(n+1)]
for _ in range(e):
    start, to, dist = map(int, input().split())
    adjL[start].append([to, dist])
    adjL[to].append([start, dist])
v1, v2 = map(int, input().split())
# 1에서 v1 까지 최소 + N에서 v2 까지 최소 + v1 v2 까지 최소
# 1에서 v2 까지 최소 + N에서 v1 까지 최소 + v1 v2 까지 최소
def Dijkstra(s1, t1):
    dp = [-1] * (n+1) # 최단 경로로 해야하므로
    hq = [[0, s1]]
    while hq:
        dist, start = heapq.heappop(hq)
        for to, nd in adjL[start]:
            newD = dist + nd
            if dp[to] == -1 or dp[to] > newD:
                dp[to] = newD
                heapq.heappush(hq, [newD, to])
    return dp[t1]

oneToV1 = Dijkstra(1, v1)
oneToV2 = Dijkstra(1, v2)
v1ToV2 = Dijkstra(v1, v2)
nToV1 = Dijkstra(n, v1)
nToV2 = Dijkstra(n, v2)

ov1v2n = -1
ov2v1n = -1
if v1ToV2 >= 0:
    if v1 == 1:
        if v2 == n:
            ov1v2n = ov2v1n = v1ToV2
        else:
            if nToV2 >= 0:
                ov1v2n = v1ToV2 + nToV2
    else:
        if oneToV1 >= 0 and nToV2 >= 0:
            ov1v2n = oneToV1 + v1ToV2 + nToV2
        if oneToV2 >= 0 and nToV1 >= 0:
            ov2v1n = oneToV2 + v1ToV2 + nToV1

if ov1v2n == -1 and ov2v1n == -1:
    print(-1)
else:
    if ov1v2n == -1:
        ov1v2n = 800_001
    if ov2v1n == -1:
        ov2v1n = 800_001
    print(min(ov1v2n, ov2v1n))

풀이 방법

1. 1에서 v1까지 v1에서 v2까지 v2에서 n까지 거리를 구한다.
2. 1에서 v2까지 v2에서 v1까지 v1에서 n까지 거리를 구한다.
3. 각각의 거리에서 -1이 나오면 안되므로 검증한다.
4. v1이 1일 때와 v2가 n일때를 구분한다.
5. 마지막으로 ov1v2n과 ov2v1n이 모두 -1일 때는 길이 없으므로 -1
6. 아닌 경우에는 -1인 쪽을 800_001로 치환하고 최소 값을 출력하면 끝!

주의 사항

• v1이 1이 아니라는 보장이 없고
• v2가 n이 아니라는 보장이 없다.
• 대신 v1은 n이 아니라는 조건과 v2는 1이 아니라는 조건은 있었다.

느낀점

• 입력 조건을 꼼꼼하게 읽지 않으면 틀릴 문제.