Floyd最小环模板
需要开两个矩阵
void floyd(){ 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,dis[i][j]+arr[j][k]+arr[k][i]); } } 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) cout<<"It's impossible."<<endl; else cout<<ans<<endl; }
例题:HDU1559
#include<bits/stdc++.h> using namespace std; const int N=110; const int INF=1e8; int arr[N][N]; int dis[N][N]; int n,m; int ans=INF; void floyd(){ 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,dis[i][j]+arr[j][k]+arr[k][i]); } } 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) cout<<"It's impossible."<<endl; else cout<<ans<<endl; } int main(){ ios::sync_with_stdio(0); while(cin>>n>>m){ for(int i=0;i<=n;i++){ for(int j=0;j<=n;j++){ arr[i][j]=INF; dis[i][j]=INF; } } int x,y,z; for(int i=1;i<=m;i++){ cin>>x>>y>>z; if(arr[x][y]>z){ arr[x][y]=arr[y][x]=z; dis[x][y]=dis[y][x]=z; } } floyd(); } return 0; }