No Caffeine, No Life

プログラミング(主にPython)

ワーシャルフロイド法

ABC 073 D - joisino's travel:ダイクストラ法、ワーシャルフロイド法、組み合わせ(itertools)

問題: D: joisino's travel - AtCoder Beginner Contest 073 | AtCoder 解説: 訪れる町が個と少ない。そこで、全通りの順列を全探索。 各点から各点への最短距離はダイクストラ法で求める。負の距離が無いし。 と、コンテスト中は考えた。これでうまくいく…

AOJ GRL_1_C:全点対間最短経路 ワーシャルフロイド法 (Warshall-Floyd's Algorithm)

全点対間最短経路問題 (APSP: All Pairs Shortest Path)を解くアルゴリズムのひとつにワーシャルフロイド法がある。 特徴: Gに負の閉路がない限り、Gに負の重みをもつ辺が存在しても適用可。 Gに負の閉路があるかどうかの判定に使える。すなわち、ある頂点v…