floyd求最小环 模板

题目 题意: 给定n个点m条边的无向图，求最小环，最小环保证至少三个点且环上没有重复节点。 思路: floyd. 容易想到的是，对于某个点k，包含他的最小环可以通过枚举另外两个相邻节点i、j再算上两点之间的最短路f[i][j]。但是！有个问题，导致会寄，你并不知道f[i][j]是否通过k。 于是乎，可以用floyd动态更新。因为floyd其实是动态规划，对于第k层循环，在更新前，任意两点之间的最短路要求只用编号[1,k)的节点。那么我以k为上述描述的枚举的点，f[i][j]之间的最短路此时是没有更新过k点的，所以不可能经过k点，就满足了环的定义。这个k比i、j要大，图中所有环的最大编号也无非是[1,n]，floyd过程中可以把所有1-n为最大编号的最小环求出。自然可以求出图中的最小环。 时间复杂度: O(n^3) 代码:

#include
using namespace std;
#define fir(i,a,b) for(int i=a;i