We are not the god,but flying in the sky.
Flying in the sky.
----imky
对于一个最小圈，它必然存在一个编号最大的顶点，比如为 k，那么在执行 Floyd-Warshall 算法的第 k 次外层迭代前，d[i][j] 存放的是中间顶点在集合 {1,2,...,k-1} 中，i 到 j 的最短路径。容易知道此时 d[i][k]+dist[k][j]+A[j][i] 就是最大编号为 k、包含 i、j、k（绕向为 j->i->k）的最小圈。做完 n 次迭代后，我们就可以知道最大编号为任意值的最小圈：最大编号为1的最小圈、最大编号为2的最小圈、……、最大编号为n的最小圈，这些值中取最小值即可。