[백준] 5719 거의 최단 경로

---

최단 경로에 속한 경로를 모두 제외한 '거의 최단 경로'를 구하는 문제이다.

 

 최단 경로를 먼저 구해야 하기 때문에 다익스트라 알고리즘을 사용하였다. 다익스트라 알고리즘을 구현할 때 경로를 구하기 위해서 이전 노드를 저장한다. 기존의 다익스트라와 다르게 이전 노드 하나만 저장하는 것이 아니라 모두 저장해야 다익스트라를 여러번 사용하지 않는다. (처음에 하나만 저장 했다가 시간초과가 발생하였다.)

 

그리고 모든 최단 경로를 구하기 위해서 distance[v] >= distance[u] + weight(v)와 같이 비교하였는다. 하지만 위와 같이 작성하면 방문할 노드를 담고있는 우선순위 큐에 불필요한 노드가 삽입되기 때문에 메모리 초과가 발생한다.

 

따라서 distance[v] > distance[u] + weight(v)인 경우, distance를 업데이트하고 우선순위 큐에 해당 노드를 삽입하고

distance[v] == distance[u] + weight(v)인 경우에는 이전 노드를 담고있는 리스트에만 추가하여 메모리 초과를 피할 수 있다.

 

그리고 최단 경로에 속한 경로를 모두 제거하고 다익스트라를 한 번 더 사용하면 거의 최단 경로의 길이를 구할 수 있다.

 

경로를 제거하는 것 이외에는(사실 이 부분이 핵심인 듯 하다.) 알고리즘 자체는 어렵지 않았으나, 메모리 초과와 시간 초과 등 제약이 타이트하여 해결하기 힘든 문제였다.

from sys import stdin
from collections import deque
import heapq

readline = stdin.readline

INF = 500 * 10 ** 3 + 1 

def get_almost_shortest():
    graph = [[] for _ in range(N)]

    for _ in range(M):
        u, v, c = map(int, readline().split())
        graph[u].append([c, v])

    pred_list, dist = dijikstra(graph)
    delete_path(graph, pred_list, dist)
    pred_list, dist = dijikstra(graph)

    return dist[end] if dist[end] < INF else -1
    
def delete_path(graph, pred_list, dist):
    q = deque()
    q.append(end)
    while q:
        n = q.popleft()
        # 해당 노드의 이전 노드 중
        for p in pred_list[n]:
            for i in range(len(graph[p])):
                # 최단 경로를 구성하는 경로 중 하나일 경우
                # 해당 비용을 무한대로 설정한다.
                if graph[p][i][1] == n and dist[n] == graph[p][i][0] + dist[p]:
                    graph[p][i][0] = INF
                    q.append(p)        
        

def dijikstra(graph):
    dist = [INF] * N
    dist[start] = 0
    pred_list = [[] for _ in range(N)]
    q = []
    heapq.heappush(q, [0, start])

    while q:
        w, u = heapq.heappop(q)
        if u == end:
            break
        if w > dist[u]:
            continue
        
        for _w, v in graph[u]:
            
            if dist[v] > dist[u] + _w:
                dist[v] = dist[u] + _w
                pred_list[v].append(u)
                heapq.heappush(q, [dist[v], v]) 

            if dist[v] == dist[u] + _w:
                pred_list[v].append(u)

    return pred_list, dist


def get_path(pred, start, end):
    path = []
    node = end
    while pred[node] != node:
        path.append(node)
        node = pred[node]
    path.append(node)    
    return list(reversed(path))

if __name__ == "__main__":
    N, M = map(int, readline().split())
    while not (N == 0 and M == 0):
        start, end = map(int, readline().split())
        print(get_almost_shortest())
        N, M = map(int, readline().split())