思路 : Floyd 实质 dp ,优化掉了第三维. dp [ i ] [ j ] [ k ] 指的是前k个点优化后    i  ->  j   的最短路。

所以我们就可以利用这个性质去求 最小环，最小环的构成可以看作是由一条  i -> k    k->j   加上 dp [ i ] [ j ]的最短路

那么我们可以利用  还没有用 k 优化的  i - >j 的最短路 去求，这样保证了 ，这是一个真正的环。

#include
     
      #include
      
       using namespace std;#define maxn 123#define inf 1e8int dis[maxn][maxn],n,key;int gra[maxn][maxn],m,id;int u,v,w,pre[maxn][maxn],ans[maxn];void floyd(){    key=inf;    for(int k=1; k<=n; k++)    {        for(int i=1; i
       
        dis[i][k]+dis[k][j])                {                    dis[i][j]=dis[i][k]+dis[k][j];                    pre[i][j]=pre[k][j];                }    }}int main(){    while(~scanf("%d%d",&n,&m))    {        key=inf;        for(int i=1; i<=n; i++)            for(int j=1; j<=n; j++)            {                gra[i][j]=dis[i][j]=inf;                pre[i][j]=i;            }        for(int i=0; i