Floyd求最小环

使用Floyd算法求最小环

Floyd

Floyd算法原理是对于点k = [1..n]，尝试用它来松弛边(u, v)。在实现时维护 $ dist[n][n] $ 数组，用来表示i和j之间可以通过$ 1..k $的最短路径。因此算法复杂度为 $ O(n^3) $ ，能计算任意两点最短路径，能够处理负边。
Floyd计算最小环时，考虑k的两个邻居i和j，他们三者可以构成一个至少有三条边的环（其中实际不存在的边边权为无穷大）。
事实上查看算法可以发现计算最小环的操作位于Floyd算法k循环松弛操作的上方，也就是在用k松弛i和j前先计算经过k的最小环，这么做是为了防止重复计算经过同一点的最小环。

注意点

1. 一开始定义const int inf的时候不能设太大，不然容易wrap掉
2. 遍历k要放在最外层