iamyoungbin

You’ll never forget my name

1 분 소요

Problem

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

Idea

거의 최단 경로는 시작점과 도착점 사이의 최단 경로에 포함되는 간선을 사용하지 않은 최단 경로를 의미한다.

다익스트라 알고리즘과 너비 우선 탐색을 이용하여 다음과 같이 구현했다.

  1. 다익스트라 알고리즘을 이용해 시작점 S로부터 다른 모든 정점까지의 최소 비용 dist를 구한다.
  2. 도착점 D를 출발점으로 하여 BFS를 하며 최단 경로에 포함된 간선들을 제외한다. 탐색 중의 임의의 두 정점에서, 출발 지점(u)까지의 최소 비용 값에서 간선 가중치(w)를 뺐을 때 도착 지점(v)까지의 최소 비용 값이 된다면 S->D의 최단 경로에 포함된다(dist[u] - w == dist[v]).
  3. 2.를 통해 얻은 최단 경로에 포함된 간선들을 제외한 간선 집합을 이용하여 다시 다익스트라 알고리즘을 이용해 S부터 D까지의 최소 비용을 구한다.

Code

import sys
import heapq
from collections import deque

def dijkstra(start):
    dist[start] = 0
    heap = []
    heapq.heappush(heap, (0, start))
    
    while heap:
        cd, cn = heapq.heappop(heap)
        
        if cd > dist[cn]:
            continue
        
        for weight, nn in edge[cn]:
            if cd + weight < dist[nn] and existed[cn][nn]:
                dist[nn] = cd + weight
                heapq.heappush(heap, (dist[nn], nn))
                
def bfs(start, end):
    queue = deque()
    queue.append(start)
    
    while queue:
        cn = queue.popleft()
        
        for weight, nn in back_edge[cn]:
            if dist[nn] == dist[cn]-weight and existed[nn][cn]:
                existed[nn][cn] = False
                queue.append(nn)   

input = sys.stdin.readline

while True:
    N, M = map(int, input().split())
    if N == 0 and M == 0:
        break
    
    S, D = map(int, input().split())
    edge = [[] for _ in range(N)]
    back_edge = [[] for _ in range(N)]
    existed = [[False for _ in range(N)] for _ in range(N)]
    for _ in range(M):
        U, V, P = map(int, input().split())
        edge[U].append((P, V))
        back_edge[V].append((P, U))
        existed[U][V] = True
    
    dist = [sys.maxsize for _ in range(N)]
    dijkstra(S)
    bfs(D, S)
    dist = [sys.maxsize for _ in range(N)]
    dijkstra(S)
    
    if dist[D] == sys.maxsize:
        dist[D] = -1
    print(dist[D])

Comment

참고