1. 문제 설명

거의 최단 경로

2. 문제 분석

다익스트라 알고리즘을 사용해 최단 경로를 얻어내고, BFS를 통해 최단 경로에 사용된 간선을 제거할 수 있다. 이후 다익스트라 알고리즘을 사용하면서 (이때 이전의 간선은 사용할 수 없다) 거의 최단 경로를 얻는다.

1. 최단 경로를 구하기 위해 다익스트라 알고리즘을 사용하자.
2. 최단 경로에 사용된 간선을 확인하기 위해 BFS를 사용해 접근하자.
3. 조건은 목적지에서 거꾸로 출발지로 향하면서 인접 노드에서 여기까지 오는 비용이 최단 경로 distances에 기록된 비용과 일치한다면 곧 최단 경로를 얻는 데 사용한 노드라는 점이다. 즉 distances[post_node] + post_cost == distances[cur_node].
4. 다시 한 번 다익스트라 알고리즘으로 거의 최단 경로를 찾는다. 목적지까지 거리가 무한이라면 찾을 수 없다는 뜻.

• 최단 경로에 사용된 경로를 어떻게 비활성화할 수 있을지가 문제를 푸는 관건이었다. 처음에는 path로 리스트 자체를 BFS에 넣어서 전달해서 비활성화했는데, 이 경우 메모리 초과가 났기 때문에 방향 그래프 자체를 거꾸로 만든 뒤 도착지에서 목적지로 향하면서 최단 경로가 맞는지 확인해야 했다. 이런 접근법을 기억하자.

3. 나의 풀이

import sys
import heapq
from collections import deque

INF = sys.maxsize

while True:
    n, m = map(int, sys.stdin.readline().rstrip().split())
    if n == 0 and m == 0: break
    nodes = [[] for _ in range(n)]
    nodes_inv = [[] for _ in range(n)]
    edges = [[False for _ in range(n)] for _ in range(n)]
    s, d = map(int, sys.stdin.readline().rstrip().split())

    for _ in range(m):
        u, v, p = map(int, sys.stdin.readline().rstrip().split())
        nodes[u].append([v, p])
        nodes_inv[v].append([u, p])

    def Dijstra():
        distances = [INF for _ in range(n)]
        distances[s] = 0

        pq = []
        heapq.heappush(pq, [0, s])

        while pq:
            cur_cost, cur_node = heapq.heappop(pq)

            if distances[cur_node] < cur_cost: continue

            for next_node, next_cost in nodes[cur_node]:
                if edges[cur_node][next_node]: continue
                if distances[next_node] > next_cost+cur_cost:
                    distances[next_node] = next_cost+cur_cost
                    heapq.heappush(pq, [next_cost+cur_cost, next_node])

        return distances

    def BFS():
        queue = deque()
        queue.append(d)

        while queue:
            cur_node = queue.popleft()

            if cur_node == s: continue

            for post_node, post_cost in nodes_inv[cur_node]:
                if distances[post_node] + post_cost == distances[cur_node] and not edges[post_node][cur_node]:
                    # cur_node로 향하는 이전 간선 비용을 사용했을 때 distances에 기록된 비용이라면 곧 최단 경로에 사용했다는 뜻이다.
                    edges[post_node][cur_node] = True
                    queue.append(post_node)

    distances = Dijstra()
    BFS()
    distances = Dijstra()
    if distances[d] == INF: print(-1)
    else: print(distances[d])