kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

GRL_1_C: All Pairs Shortest Path (続き)

さっぱりアイデアがつながってこない感じ

と思ったけどなんか1日たったら通った
通してみると、ダイクストラ法より、なんていうか、素朴な感じ?

隣接行列って書いてあるのは隣接行列が特に便利っていう意味なんだろうか

ていうか答えがn歩目の隣接行列って感じだった

たとえば、隣接行列で頂点1から頂点2までの距離が5だったとする
そしたら隣接行列で始点が頂点2のところをみる
頂点2から頂点3までの距離が3だったら、頂点1から頂点2を経由した
頂点3までの距離は8ということになる
それまでの記録が9以上だったら更新する
これを更新がなくなるまで繰り返す
もし途中で、頂点nから頂点nまでの重みが負になったら負のサイクルだということ

わざわざメモ化した意識はないんだけれども
それまでに求めた最短距離を使ってるからメモ化したことになるのかな

INF = 2000000000
NEG = -1
COMP = 0
CONT = 1

def read_adj_mat():
    nv, ne = [int(x) for x in input().split()]
    A = [[0 if fr == to else INF for fr in range(nv)] for to in range(nv)]
    for _ in range(ne):
        s, t, d = [int(x) for x in input().split()]
        A[s][t] = d
    return A

def step(A):
    result = COMP
    n = len(A)
    D = [fr[:] for fr in A]
    for fr in range(n):
        for to in range(n):
            here = A[fr][to]
            if fr == to or here == INF:
                continue
            for to2 in range(n):
                here2 = A[to][to2]
                if to == to2 or here2 == INF:
                    continue
                new = here + here2
                if fr == to2 and new < 0:
                    return NEG, None
                elif new < D[fr][to2]:
                    D[fr][to2] = new
                    result = CONT
    return result, D

def get_shortest_paths(A):
    while True:
        result, D = step(A)
        if result == NEG:
            return NEG, None
        elif result == COMP:
            return COMP, D
        A = D

def print_result(D):
    for fr in range(len(D)):
        for to in range(len(D)):
            if to != 0:
                print(" ", end="")
            if D[fr][to] == INF:
                print("INF", end="")
            else:
                print(D[fr][to], end="")
        print()

def main():
    A = read_adj_mat()
    result, D = get_shortest_paths(A)
    if result == NEG:
        print("NEGATIVE CYCLE")
    else:
        print_result(D)

if __name__ == '__main__':
    main()

ここ最近ではめずらしいことにTLEせずに終了
オーダはとてもわかりやすく3乗だな 3乗でよかったんだ

最短距離はわかるけど最短の経路は記録してない
記録は・・・頑張ればできるかな