问题：

给出一个图，问其中的有 \(n\) 个节点构成的边权和最小的环 \((n\geq 3)\) 是多大。

暴力做法：

删除掉 \(u\) 和 \(v\) 之间的边，如何求出u\to v的不经过该边的最短路，加上该边即可。

\(Dijsktra\)：

在暴力算法的基础上，优化求最短路的过程。
枚举所有边，每一次求删除一条边之后对这条边的起点跑一次 \(Dijkstra\)，道理同上。
复杂度：\(O(m*nlogn)\)

\(Floyd\)：

记原图中\(u,v\) 之间边的边权为 \(val(u,v)\)。
\(Floyd\) 算法有一个性质：
当外层循环到 \(k\) （尚未开始第 \(k\) 次循环）时，最短路数组 \(dis[u][v]\)中， 表示的是从 \(u\) 到 \(v\) 且仅经过编号在 \([1,k)\) 区间中的点的最短路。
  显然，一个环可以表示为 \(u \to v\) 的不经过点 \(k\) 的最短路\(+ u\)到 \(k\) 的距离\(+ v\)到 \(k\) 的距离。但是正常的 \(Floyd\) 算法过程中，点 \(k\) 会把任意两点之间的最短路更新。如果 \(u\) 到 \(v\) 的最短路中出现了 \(k\) ，那么就不满足要求。
可以采用如下做法：
  由最小环的定义可知其至少有三个顶点，设其中编号最大的顶点为 \(maxn\)，环上与 \(maxn\) 相邻两侧的两个点为 \(u,v\) ，则在最外层循环枚举到 \(maxn\) 时，
该环的长度为：\(val(u,v)+val(u,maxn)+val(v,maxn)\)。
故在循环时对于每个 \(k\)，枚举满足 \((i<k,j<k)\) 的 \(i,j\)，更新答案即可。
复杂度：\(O(n^3)\)

代码实现：

int floyd(int n)
{
    int ans=inf;
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<k;i++)
            for(int j=i+1;j<k;j++)
                ans=min(dis[i][j]+pic[i][k]+pic[k][j],ans);//最小环
        for(int i=1;i<=n;i++)//正常的Floyd求最短路
            for(int j=1;j<=n;j++)
                dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);
    }
    return ans;
}

模板：【HDU-1599】

#include <bits/stdc++.h>
using namespace std;
const int inf=1e8;
int dis[105][105],pic[105][105];
int floyd(int n)
{
    int ans=inf;
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<k;i++)
            for(int j=i+1;j<k;j++)
                ans=min(dis[i][j]+pic[i][k]+pic[k][j],ans);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);
    }
    return ans;
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dis[i][j]=inf;
                if(i==j)
                    dis[i][j]=0;
                pic[i][j]=dis[i][j];
            }
        }
        for(int i=1;i<=m;i++)
        {
            int x,y,w;
            scanf("%d%d%d",&x,&y,&w);
            dis[x][y]=min(dis[x][y],w);
            dis[y][x]=dis[x][y];
            pic[x][y]=pic[y][x]=dis[x][y];
        }
        int ans=floyd(n);
        if(ans==inf)
            printf("It's impossible.\n");
        else
            printf("%d\n",ans);
    }
    return 0;
}