[백준] 5719 - 거의 최단 경로 (Python)

문제 해결의 기본적인 아이디어는 먼저 최단거리를 구한 후, 그래프에 최단 경로에 포함되는 간선을 모두 지운 뒤 한번 더 최단거리를 구하는 것이다.

최단 경로에 포함되는 경로를 찾으려면 어떻게 해야 할까? 먼저, 다익스트라 알고리즘을 사용해서 최단 경로의 길이를 구했다고 가정해 보자.

가장 먼저 생각나는 것은 완전탐색으로 모든 경로를 탐색한 뒤 최종 경로의 길이가 최단 경로와 같은 간선을 모두 지우는 것이다.

하지만 더 효율적인 방법이 있다. 도착지점부터 거꾸로 되짚어 나가는 것이다. 모든 정점까지의 최단거리를 알고 있으므로 최단거리가 아닌 정점은 바로 배제가 가능하다.

간선을 그래프에서 바로 제거하는 것은 비효율적이므로 모든 간선에 번호를 붙인 뒤 그것을 인덱스로 하는 배열을 만든다.
최단 경로에 포함되는 간선에만 체크를 해서 최단 경로 간선 여부를 판별하면 된다.

---

import sys, math, heapq
input = sys.stdin.readline

# 다익스트라
def dijk(start):
    dist[start] = 0 
    queue = [start]
    while queue:
        u = heapq.heappop(queue)
        for i, v, p in graph[u]:
        	# 간선 i가 최단경로 간선에 포함되어 있으면 사용하지 않음
            if not is_shortest_path[i] and dist[u]+p < dist[v]:
                dist[v] = dist[u]+p 
                heapq.heappush(queue, v)
                
def find_shortest_path(end):
	# 역방향으로 dfs
    stack = [end]
    while stack:
        v = stack.pop()
        for i, u, p in re_graph[v]:
        	# 이전에 지나가지 않은 간선 u->v가 최단경로에 포함되는 경우
            if not is_shortest_path[i] and dist[v] == dist[u]+p:
            	# i는 최단경로 간선에 포함
                is_shortest_path[i] = 1
                stack.append(u)

while True: 
    n, m = map(int, input().rstrip().split())
    if n == 0: # 종료
        break
        
    graph = [[] for _ in range(n)]
    # 역방향 그래프
    re_graph = [[] for _ in range(n)]
    # 최단 경로에 포함되는 간선을 체크
    is_shortest_path = [0]*m
    
    s, d = map(int, input().rstrip().split())
    
    for i in range(m):
        u, v, p = map(int, input().rstrip().split())
        # 최단경로 간선인지 판별하기 위해 번호 부여
        graph[u].append((i, v, p))
        re_graph[v].append((i, u, p))
    
    # 최단경로 초기화
    dist = [math.inf]*n
    dijk(s)
    # 최단경로에 포함되는 간선 찾기 
    find_shortest_path(d)
    
    dist = [math.inf]*n 
    dijk(s)
    # 거리가 inf일 경우 -1 출력
    print(dist[d] if not math.isinf(dist[d]) else -1)