每两点间最短路问题（APSP问题）!

此类问题使用Floyd-Warshall算法解决。它是动态规划算法。

1. 状态表示：f(i,j)表示从点 i 到点 j 的最短距离。

2. 状态转移方程：f(i,j)＝min{f(i,k)＋f(k,j)}  （i 到 k、k 到 j 都是连通的） 3. 时间复杂度：O(n3)

int f[N][N], prev[N][N]; // 追踪prev可以得到最短路。 int len=INF;     // 最小环的长度 void Floyd() { // 初始化——可以在读图时完成 for (int i=0; i<n; i++)   for (int j=0; j<n; j++)    f[j] = G[j];   memset(prev, -1, sizeof(prev)); /* len=INF; */ // 计算。注意，k在最外面。  for (int k=0; k<n; k++) {   /* 如果求最小环，请将下面的代码插入到这里。 */   for (int i=0; i<n; i++)    for (int j=0; j<n; j++)     if (f[k] + f[k][j] < f[j])     {      f[j] = f[k] + f[k][j];      prev[j] = k;     } } } // cout<<f[j]<<endl; // 通过递归调用追踪prev，就可以得到最短路径上的结点。

Floyd算法可以用来求最小环（无向图！）。将以下代码插入到上面的标记处即可。

for (int i=0; i<k; i++)  for (int j=i+1; j<k; j++)   len = min(len, G[j]+f[k]+f[k][j]);  

// G是无向图！len为最小环的和