[백준] 거의 최단경로

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

5719번: 거의 최단 경로

다익스트라와 BFS를 통해 풀이하였습니다. 이 문제의 포인트는 최단 경로를 구성하는 간선들을 지워줘야합니다. 먼저, 다익스트라를 통해서 각 정점까지의 최단 경로의 길이를 구해줍니다. 그 다음으로는 역방향 그래프를 BFS로 탐색하면서 최단 경로를 구성하는 간선들을 지워주면 됩니다. 다익스트라를 통해 dist 배열에는 각 정점까지의 최단 경로의 길이가 저장 되어 있습니다. 최단 경로를 구성하는 간선을 파악하는 방법은 다음 노드의 dist길이와 다음 노드로 가는 간선의 길이의 합이 현재노드의 dist 값과 같으면 제거해주면 됩니다. 만약, dist[5] = 10이고 dist[3] = 6인데 5 -> 3으로 가는 간선의 길이가 4이면 해당 간선은 5번 정점을 최단 경로의 길이로 갱신하는 간선이므로 지워주면 됩니다.

 

import sys, heapq
from collections import defaultdict, deque
INT_MAX = sys.maxsize
#sys.stdin = open("input.txt", "r")
input = sys.stdin.readline


def dijkstra(graph, start, dist, isValid):
    dist[start] = 0
    q = [(0, start)]

    while q:
        d, cur = heapq.heappop(q)

        if dist[cur] > d:
            continue

        for next_node, next_weight in graph[cur]:
            # 유효하지 않은 간선인 경우
            if not isValid[cur][next_node]:
                continue

            next_dist = d + next_weight

            if dist[next_node] > next_dist:
                dist[next_node] = next_dist
                heapq.heappush(q, (next_dist, next_node))


def removeEdge(graph, dist, start, isValid, n):
    q = deque([start])
    visited = [False] * n

    visited[start] = False

    while q:
        cur = q.popleft()

        for next_node, next_weight in graph[cur]:
            # 현재 노드를 최단 거리로 갱신하는 간선인 경우 비활성화 한다.
            if dist[cur] == dist[next_node] + next_weight:
                isValid[cur][next_node] = False
                isValid[next_node][cur] = False

                if not visited[next_node]:
                    visited[next_node] = True
                    q.append(next_node)

while True:
    n, m = tuple(map(int, input().split()))

    # 종료조건
    if n == 0 and m == 0:
        break

    start, dest = tuple(map(int, input().split()))

    graph = defaultdict(list)
    reverse_graph = defaultdict(list)

    isValid = [
        [False] * n
        for _ in range(n)
    ]

    for _ in range(m):
        fr, to, weight = tuple(map(int, input().split()))

        graph[fr].append((to, weight))
        reverse_graph[to].append((fr, weight))

        isValid[fr][to] = True
        isValid[fr][to] = True

    dist = [INT_MAX] * n

    dijkstra(graph, start, dist, isValid)

    # 역방향 그래프를 기반으로 현재 노드를 최단 거리로 갱신하는 간선들을 제거한다.
    removeEdge(reverse_graph, dist, dest, isValid, n)

    dist = [INT_MAX] * n
    # 제거된 간선을 기반으로 다시 한번 최단 경로를 찾는다.
    dijkstra(graph, start, dist, isValid)

    if dist[dest] == INT_MAX:
        print(-1)
    else:
        print(dist[dest])