ワーシャルフロイド法 - minus9d-prog-contest

ワーシャルフロイド法

基本実装

code:cpp

vector<vector<ll>>d(n,vector<ll>(n,INF));

rep(k,0,n)rep(i,0,n)rep(j,0,n)chmin(dij,dik+dkj);

応用

辺を後から追加

https://atcoder.jp/contests/abc416/submissions/67907499 に実装例あり。（この実装例では、仮想の頂点を1個追加している関係でn+1回ループを回している。下のコードスニペットは頂点数nとして書き直した)

code:cpp

// 頂点x, yの間にコストtの辺を新たに張る

rep(i,0,n)rep(j,0,n){

chmin(dij,dix+t+dyj);

chmin(dij,diy+t+dxj);

}