문제

[백준] 거의 최단 경로 (Platinum 5)

요약

거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 것을 말한다. 거의 최단 경로의 길이를 출력하라.

분류

  • 다익스트라

풀이

1. 내 풀이 (다익스트라 + BFS + 해시 셋)

최단 경로에 해당하는 경로들을 HASHSET에 보관하고, HASHSET에 없는 경로들만 사용하여 최단 경로를 다시 탐색한다.

from collections import deque
import sys
from heapq import *
input = sys.stdin.readline
INF = sys.maxsize

while True:
    n, m = map(int, input().split())
    if n == 0 and m == 0:
        break
    s, d = map(int, input().split())

    # 그래프 생성
    graph = [[] for _ in range(n)]
    for _ in range(m):
        a, b, c = map(int, input().split())
        graph[a].append((b, c))

    # 다익스트라 수행
    hq = [(0, s)]
    dist = [INF] * n
    # 경로 기록을 위한 2차원 리스트
    path = [[] for _ in range(n)]

    while hq:
        w, i = heappop(hq)

        if dist[i] < w:
            continue

        for node, weight in graph[i]:
            if dist[node] > weight + w:
                dist[node] = weight + w
                heappush(hq, (dist[node], node))
                path[node] = [i]
            elif dist[node] == weight + w:
                path[node].append(i)

    # 경로 탐색
    x = d
    q = deque([x])
    # 최단 경로에 포함되는 경로를 SET에 저장
    shortest_edges = set()
    visit = set()
    while q:
        cur = q.popleft()
        if cur in visit:
            continue
        visit.add(cur)
        for v in path[cur]:
            shortest_edges.add((v, cur))
            if cur != s:
                q.append(v)

    hq = [(0, s)]
    dist = [INF] * n

    while hq:
        w, i = heappop(hq)

        if dist[i] < w:
            continue

        for node, weight in graph[i]:
            # 최단 경로에 해당하지 않는 경로들만으로 탐색
            if (i, node) in shortest_edges:
                continue
            if dist[node] > weight + w:
                dist[node] = weight + w
                heappush(hq, (dist[node], node))

    print(dist[d] if dist[d] != INF else -1)