题意：
思路：
先要明白f l o y d的原理。
赛时完全不会写求最小环了。
f l o y d中，先枚举中间点k，这样i − > j的路径都是由[ 1 , k − 1 ]的点构成的。所以这样k − > i − > j − > k就会构成一个环，求当前环的权值就好。更新完环的权值后，再更新最短距离。
这题有一个小细节就是，此题的数组初始化为0 x 3 f 3 f 3 f 3 f,会爆i n t
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define rep(i, a, b) for(int i=(a);i<=(b);++i) #define dep(i, a, b) for(int i=(a);i>=(b);--i) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=1e5+100,inf=0x3f3f3f3f; ll g[110][110],f[110][110]; int main(){ int n=read,m=read; rep(i,1,n) rep(j,1,n) if(i!=j) g[i][j]=f[i][j]=inf; rep(i,1,m){ ll u=read,v=read,w=read; g[u][v]=g[v][u]=min(g[u][v],w); f[u][v]=f[v][u]=min(w,f[u][v]); } ll 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(ans,f[i][j]+g[k][i]+g[j][k]); //cout<<ans<<endl; } } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ f[i][j]=min(f[i][j],f[i][k]+f[k][j]); f[j][i]=f[i][j]; } } } if(ans==inf) puts("No solution."); else cout<<ans<<endl; return 0; }
