[파이썬]백준 1504 특정한최단경로

링크

백준 1504 특정한최단경로

무향그래프에서의 다익스트라 문제이다.
그러나 다른점은 경로상에서 반드시 경유해야 하는 두 정점 stop1과 stop2가 존재한다는 점이다.

이경우 생길 수 있는 경로는 2가지 이다.
시작정점 -> stop1 -> stop2 -> 도착정점
시작정점 -> stop2 -> stop1 -> 도착정점

각 구간(ex.시작정점 -> stop1)을 시작점과 도착점으로 하는 최단경로를 구한다.
그리고 이를 모두 더해주면 본래 구해야 하는 경로의 최단경로를 구할 수 있다.

그후 두가지 경로를 비교해 더 작은 값을 출력하면 된다.
단, 경로가 없을 경우엔 -1를 출력하는데, 코드상에선 경로의 합이 0xffffff보다 큰 경우가 그러한 경우이다. (방문하지 못해 가중치 갱신이 안됐기 때문)

정답 코드

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

def dijkstra(start, end):
    dis = [0xffffff] * (N + 1)
    dis[start] = 0
    q = [[0, start]]
    while q:
        k, u = heappop(q)
        if k > dis[u]: continue
        for w, v in G[u]:
            if dis[v] > dis[u] + w:
                dis[v] = dis[u] + w
                heappush(q, [dis[v], v])

    return dis[end]

N, E = map(int, input().split())
G = [[] for _ in range(N + 1)]
for _ in range(E):
    u, v, w = map(int, input().split())
    G[u].append([w, v])
    G[v].append([w, u])

stop1, stop2 = map(int, input().split())

# 1 -> stop1 -> stop2 -> N
path1 = dijkstra(1, stop1) + dijkstra(stop1, stop2) + dijkstra(stop2, N)
# 1 -> stop2 -> stop1 -> N
path2 = dijkstra(1, stop2) + dijkstra(stop2, stop1) + dijkstra(stop1, N)

if path1 >= 0xffffff and path2 >= 0xffffff:
    print(-1)
else:
    print(min(path1, path2))

알게된 것👨‍💻

• 중간에 경유를 하더라도 최단 경로를 찾는 방법!