Floyd算法求最小环

先放代码，再证明算法的正确性。

证明

我们给一个图做一个编号(1–n)，也就是表示n个点。
对于每一个环（不包括自环），我们取这个环上点的最大编号k。
那么也就说与k相邻的两个点的编号小与k，我们记为 i 和 j 。
那么 i 与 j 之间的最短路经过点的编号显然小与 k ，不然 k 就要被赋予这个更大的值
那么我们跑 k-1 次循环就可以找到 i 与 j 的最短路。
我们假设最短路长度是dis(i, j)。那么这个环长度就是dis(i,j) + val(i,k) + val(k,j)
$val(i,j)表示i与j边的长度，没有则设为inf$val(i,j)表示i与j边的长度，没有则设为inf
这样我们就可以通过枚举k，然后枚举与k相邻的边。

模板题