最小环 Floyd 算法 无向图的最小环问题

P6175 无向图的最小环问题 - 洛谷

k次插点前更新 ans=min(d[i][j]+w[j][k]+w[k][i])
注意 i，j下边循环范围小于k

// Floyd 最小环 O(n^3)
#include<bits/stdc++.h>
using namespace std;const int N=110;
int n,m,a,b,c,ans=1e8;
int w[N][N],d[N][N];int main(){cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i!=j) w[i][j]=1e8;for(int i=1;i<=m;i++){cin>>a>>b>>c;w[a][b]=w[b][a]=min(w[a][b], c);//去重边}memcpy(d,w,sizeof w);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,d[i][j]+w[j][k]+w[k][i]);for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);}if(ans==1e8) puts("No solution.");else printf("%d\n",ans);
}

https://oi-wiki.org/graph/shortest-path/#floyd-算法
最小环 - OI Wiki