传送门
floyd求最小环的板子题目。
就是枚举两个相邻的点求最小环就行了。
代码：
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f
#define ll long long
using namespace std;
inline ll read(){
ll ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
ll dis[105][105],f[105][105],ans;
int n,m;
int main(){
while(~scanf("%d%d",&n,&m)){
for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)dis[i][j]=f[i][j]=inf;
for(int i=1;i<=m;++i){
int u=read(),v=read();
ll w=read();
dis[u][v]=dis[v][u]=f[u][v]=f[v][u]=min(f[u][v],w);
}
ans=inf;
for(int k=1;k<=n;++k){
for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)
if(i!=j&&j!=k&&k!=i)ans=min(ans,dis[i][j]+f[i][k]+f[k][j]);
for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
if(ans==inf)puts("It's impossible.");
else printf("%I64d\n",ans);
}
return 0;
}