백준 5719 : 문제링크

  • 문제유형 :

    • 그래프
    • 다익스트라 최단 경로 알고리즘

  • 설명

    • 다익스트라 최단 경로에 포함되는 모든 간선을 추적한다
    • 최단 경로에 포함되는 모든 간선을 추적할 때 DFS를 사용하여 추적하여 제외시킨다
    • 제외된 간선 외에서 다익스트라 최단 경로 알고리즘으로 차선 최단 경로를 찾는다

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    from collections import deque
    import heapq
    import sys

    input = sys.stdin.readline

    def dijkstra():
        heap_data = []
        heapq.heappush(heap_data, (0, start))
        distance[start] = 0
        while heap_data:
            dist, now = heapq.heappop(heap_data)
            if distance[now] < dist:
                continue
            for i in adj[now]:
                cost = dist + i[1]
                if distance[i[0]] > cost and not dropped[now][i[0]]:
                    distance[i[0]] = cost
                    heapq.heappush(heap_data, (cost, i[0]))

    def bfs():
        q = deque()
        q.append(end)
        while q:
            now = q.popleft()
            if now == start:
                continue
            for prev, cost in reverse_adj[now]:
                if distance[now] == distance[prev] + cost
                    dropped[prev][now] = True
                    q.append(prev)

    while True:
        n, m = map(int, input().split())
        if n == 0:
            break
        start, end = map(int, input().split())
        adj = [[] for _ in range(n + 1)]
        reverse_adj = [[] for _ in range(n + 1)]
        for _ in range(m):
            x, y, cost = map(int, input().split())
            adj[x].append((y, cost))
            reverse_adj[y].append((x, cost))
        dropped = [[False] * (n + 1) for _ in range(n + 1)]
        distance = [1e9] * (n + 1)
        dijkstra()
        bfs()
        distance = [1e9] * (n + 1)
        dijkstra()
        if distance[end] != 1e9:
            print(distance[end])
        else:
            print(-1)