グラフのすべての2頂点間の最短路をワーシャルフロイド法で求める - minus9d's diaryワーシャルフロイド法というのを使うと、グラフのすべての2頂点間の最短路を求められるらしい。蟻本を参考にして解いてみた。 以下のグラフを例にとって、全点対の最短路を求める。 コードは以下。 #include <cstdio> #include <algorithm> #define REP(i,n) for(int i = 0; i < (int)(n); ++i) using namespace std; const int MAX_V = 200; int d[MAX_V][MAX_V]; void setCost(int d[MAX_V][MAX_V], int s, int e, int cost){ d[s][e] = d[e][s] = cost; } int main(){ // 頂点の数 const int V = 9; // 十分大きい数をとる const int INF
