warshallfloyd
(kyopro/library/graph/warshallfloyd.cpp)

• View this file on GitHub
• Last update: 2022-07-20 00:04:43+09:00
• Link: View error logs on GitHub Actions

Verified with

• kyopro/test/warshallfloyd_aoj.test.cpp

Code

/*
* @title warshallfloyd
* @docs kyopro/docs/warshallfloyd.md
*/

//ワーシャルフロイド
void WarshallFloyd(int n, vector<vector<ll>> & d) {
	rep(i, n) {//経由する頂点
		rep(j, n) {//始点
			rep(k, n) {//終点
				d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
			}
		}
	}
}

#line 1 "kyopro/library/graph/warshallfloyd.cpp"
/*
* @title warshallfloyd
* @docs kyopro/docs/warshallfloyd.md
*/

//ワーシャルフロイド
void WarshallFloyd(int n, vector<vector<ll>> & d) {
	rep(i, n) {//経由する頂点
		rep(j, n) {//始点
			rep(k, n) {//終点
				d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
			}
		}
	}
}

Back to top page