5719번: 거의최단경로 (그래프, 다익스트라) - Fastcampus

www.acmicpc.net/problem/5719

5719번: 거의 최단 경로

import sys
import heapq
import collections


def dijkstra(N, start):
    qu = []
    heapq.heappush(qu, (0, start))
    dist = [float("inf")] * N
    dist[start] = 0

    while qu:
        d, node = heapq.heappop(qu)
        if d > dist[node]:
            continue
        for w, e in graph[node]:
            nd = d + w
            if nd < dist[e] and not dropped[node][e]:
                dist[e] = nd
                heapq.heappush(qu, (nd, e))
    return dist


def bfs(start, dist):
    qu = collections.deque([start])
    visited = []

    while qu:
        node = qu.popleft()
        if node not in visited:
            visited.append(node)
            for w, e in graph_r[node]:
                if dist[e] + w == dist[node]:
                    dropped[e][node] = 1
                    qu.append(e)
    return visited

while True:
    N, M = map(int, input().split())
    if N == 0:
        break
    S, D = map(int, input().split())

    graph = [[] for _ in range(N)]
    graph_r = [[] for _ in range(N)]
    for _ in range(M):
        n1, n2, w = map(int, sys.stdin.readline().split())
        graph[n1].append((w, n2))
        graph_r[n2].append((w, n1))

    # 최단경로 찾은 후 이동불가 설정
    dropped = [[0] * N for _ in range(N)]
    dist = dijkstra(N, S)
    bfs(D, dist)

    # 거의 최단경로 찾기
    dist = dijkstra(N, S)
    print(dist[D] if dist[D] != float("inf") else -1)

 

다른 풀이

import sys
import heapq
import collections


def dijkstra(N, start, end):
    qu = []
    heapq.heappush(qu, (0, [start]))
    dist = [float("inf")] * N
    dist[start] = 0

    min_path = []
    while qu:
        d, path = heapq.heappop(qu)
        node = path[-1]
        if d > dist[node]:
            continue
        if node == end:
            min_path.append(path)

        for w, e in graph[node]:
            nd = d + w
            if nd <= dist[e] and not dropped[node][e]:  # 복수 최단경로 탐색을 위해 등호 사용 (단점: 느린 탐색)
                dist[e] = nd
                heapq.heappush(qu, (nd, path + [e]))
    return dist, min_path

while True:
    N, M = map(int, input().split())
    if N == 0:
        break
    S, D = map(int, input().split())

    graph = [[] for _ in range(N)]
    for _ in range(M):
        n1, n2, w = map(int, sys.stdin.readline().split())
        graph[n1].append((w, n2))

    # 최단경로 찾은 후 이동불가 설정
    dropped = [[0] * N for _ in range(N)]
    dist, min_path = dijkstra(N, S, D)
    for p in min_path:
        for i in range(1, len(p)):
            dropped[p[i-1]][p[i]] = 1

    # 거의 최단경로 찾기
    dist, min_path = dijkstra(N, S, D)
    print(dist[D] if dist[D] != float("inf") else -1)