[백준] 거의 최단 경로

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

최단 경로를 제외한 차선책 경로를 찾는 문제

IDEA
다익스트라로 정점간 최단경로 계산
최단경로를 통해 역방향 그래프 구축 (+ 방문처리)
두번째 다익스트라 실행

import heapq
from collections import deque
INF = 1e9
while True:
    n, m = map(int, input().split())

    if n == 0 and m == 0:
        break

    graph = [[] for _ in range(n)]
    S, D = map(int, input().split())

    for _ in range(m):
        u, v, p = map(int, input().split())
        graph[u].append((v, p))

    # 첫 번째 다익스트라 알고리즘 실행
    distance = [INF] * n
    pq = []
    heapq.heappush(pq, (0, S))
    distance[S] = 0

    while pq:
        dist, now = heapq.heappop(pq)

        if dist > distance[now]:
            continue

        for next_node, cost in graph[now]:
            new_cost = dist + cost

            if new_cost < distance[next_node]:
                distance[next_node] = new_cost
                heapq.heappush(pq, (new_cost, next_node))

    # 역방향 그래프 구축
    rev_graph = [[] for _ in range(n)]
    for u in range(n):
        for v, cost in graph[u]:
            if distance[u] + cost == distance[v]:
                rev_graph[v].append((u, cost))

    # 최단 경로에 포함되는 간선 표시
    q = deque()
    q.append(D)
    removed = [[False] * n for _ in range(n)]

    while q:
        now = q.popleft()
        for prev, cost in rev_graph[now]:
            if not removed[prev][now]:
                removed[prev][now] = True
                q.append(prev)

    # 두 번째 다익스트라 알고리즘 실행
    new_distance = [INF] * n
    pq = []
    heapq.heappush(pq, (0, S))
    new_distance[S] = 0

    while pq:
        dist, now = heapq.heappop(pq)

        if dist > new_distance[now]:
            continue

        for next_node, cost in graph[now]:
            if removed[now][next_node]:
                continue

            new_cost = dist + cost

            if new_cost < new_distance[next_node]:
                new_distance[next_node] = new_cost
                heapq.heappush(pq, (new_cost, next_node))

    if new_distance[D] == INF:
        print(-1)
    else:
        print(new_distance[D])