kb84tkhrのブログ

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

GRL_1_C: All Pairs Shortest Path (続き2)

解説を読む
ワーシャルフロイドのアルゴリズムというらしい
レナの本には名前しか出てないみたいだ
レナの本は索引がないのがよろしくないな

やってることはそっくり・・・かな?
いや?
3重にループしただけで終わってる?
それでいいの?
一発で全部最短になる?

ていうか
形は一番外側のループがtoを回すループになってるだけで
不思議なほど似てるけど
考え方が全然違ってる
経由する点をひとつずつ増やしていく、という考え方だった

オーダはとてもわかりやすく3乗だな 3乗でよかったんだ

自分のコードは3乗の周りにもうひとつループがあったな
嘘ついてましたすみません

ではコード修正
修正したところだけ

def get_shortest_paths(D):
    n = len(D)
    for to in range(n):
        for fr in range(n):
            here = D[fr][to]
            if here == INF:
                continue
            for to2 in range(n):
                here2 = D[to][to2]
                if here2 == INF:
                    continue
                D[fr][to2] = min(D[fr][to2], here + here2)

def main():
    D = read_adj_mat()
    get_shortest_paths(D)
    for d in [D[x][x] for x in range(len(D))]:
        if d < 0:
            print("NEGATIVE CYCLE")
            break
    else:
        print_result(D)

昨日のコードで一番重かったのはCase#46
頂点100個でエッジが9900個のやつ
時間は1.64sで使用メモリが7056KB

今回は0.53sで6344KB
完敗です