白準5719号:ほぼ最短経路

11749 ワード
パイ ps ダエストラ BFS テキストリンク
白準5719号:ほぼ最短経路
解法
この問題で、当番生の時もノートに手作業でエンコードしていました.本当に4時間かかりました最初、私がコードを書く方法は、いっそ幹線をディック郡から削除することで、タイムアウトしました.そこで、幹線がまだ生きているかどうかの情報を格納する2次元リストを作成しました.まず複数の曲線を回転させ,各ノードまでの最短距離を求め,その後BFSを逆方向に追跡する.このとき、幹線の重みと到達ノードの最短距離との和が出発ノードまでの最短距離に等しい場合、その幹線は最短経路に属する.それらの幹線をすべて排除して、もう一度出口を回すと、ほとんど最短経路が現れます.
正しいコード
import sys
import heapq
from collections import deque, defaultdict
input = sys.stdin.readline


def dijkstra(X):
    dist = [float('inf')] * (N)
    dist[X] = 0

    Q = list()
    heapq.heappush(Q, (0, X))

    while Q:
        SD, SN = heapq.heappop(Q)

        if dist[SN] < SD:
            continue

        for FN, FD in L[SN]:
            d = SD + FD
            if dist[FN] > d and LL[SN][FN]:
                dist[FN] = d
                heapq.heappush(Q, (d, FN))

    return dist

def bfs(X):
    Q = deque()
    Q.append(X)

    while Q:
        SN = Q.popleft()

        for FN, FD in L_reverse[SN]:
            if FD + short[FN] == short[SN]:
                if LL[FN][SN]:
                    Q.append(FN)
                    LL[FN][SN] = 0


while True:
    N, M = map(int, input().split())
    if not N or not M:
        break
    S, D = map(int, input().split())
    L = defaultdict(list)
    L_reverse = defaultdict(list)
    LL = [[0] * (N) for _ in range(N)]
    for i in range(M):
        U, V, P = map(int, input().split())
        L[U].append((V, P))
        L_reverse[V].append((U, P))
        LL[U][V] = 1

    short = dijkstra(S)
    if short[D] == float('inf'):
        print(-1)
        continue
    bfs(D)
    result = dijkstra(S)[D]
    print(result if result != float('inf') else -1)
反省点
あまり記憶に執着しないでください.
初心者からのHTML基本:パート1
マージソート