[백준] 1504번 특정한 최단 경로

백준 1504 특정한 최단 경로

노드 간의 최단 거리를 구하기 위해서BFS 탐색과 다익스트라 알고리즘을 활용해야 했다. 두 노드를 방문하고 목적지로 도달하는 경우 중에 최단 경로의 길이를 출력해야 한다. 처음엔 DP 리스트를 3차원으로 만들어 v1과 v2의 방문 여부를 포함했지만 시간 초과가 났다.

방문해야 하는 노드까지의 최단거리들을 구한 후에, 이러한 최단거리들로 목적지까지의 최단거리를 구해야 한다.

1. 1번 노드에서 v1까지의 최단 거리
2. 1번 노드에서 v2까지의 최단 거리
3. v1에서 v2까지의 최단 거리
4. v1에서 n번 노드까지의 최단 거리
5. v2에서 n번 노드까지의 최단 거리

(1 -> v1 -> v2 -> n) 와 (1 -> v2 -> v1 -> n)를 비교하여 더 작은 값이 정답이다.
이렇게 5가지를 활용하면 1차원 DP 리스트로 다익스트라 알고리즘을 구현할 수 있다.

import sys
from collections import deque

def BFS(start, end) -> int:
    dq = deque()
    dq.append([start, 0])
    dp = [1e9 for _ in range(n + 1)]
    dp[start] = 0
    res = 1e9
    while dq:
        s, c = dq.popleft()
        if s == end:
            res = min(res, c)
            continue
        for child, cost in childs[s]:
            if dp[child] > c + cost:
                dp[child] = c + cost
                dq.append([child, c + cost])
    if res == 1e9:
        print(-1)
        exit(0)
    return res

input = sys.stdin.readline
n, e = map(int, input().split())
childs = [[]for _ in range(n + 1)]

for _ in range(e):
    a, b, c = map(int, input().split())
    childs[a].append([b, c])
    childs[b].append([a, c])
t1, t2 = map(int, input().split())

a1 = BFS(1, t1)
a2 = BFS(1, t2)
b = BFS(t1, t2)
c1 = BFS(t1, n)
c2 = BFS(t2, n)
res = min(a1 + c2 + b, a2 + c1 + b)

print(res)