题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1599
题目要求求无向图中的最小环，如果只用floyd暴力求解mp[ i ][ i ]的话会发现有问题，比如1->2 , 2->3 ,得出1-> 3 ，那 3 - > 1 == 1->3 , 图就变成了1->2 , 2->3 , 3->2 , 2->1,这个讲道理不能算作一个环，那么就要用另一种方法来求最小环，
比如先用（1-k-1）松弛一下图，接着用边（i，k）和（k，j）得出另一条路径，由于 i-j 的路径还没有被k松弛过，所以（i，k）和（k，j）的路径和（i，j）的路径一定不相同，但这时我们还无法保证当前是最短的所以每个情况都要考虑到从而
得到最小的环
#include<bits/stdc++.h> using namespace std; #define INT_MAX 0x73f3f3f int mp[110][110]; int dist[110][110]; void intt(){ for(int i=0;i<110;i++) for(int j=0;j<110;j++) if(i==j) mp[i][j]=dist[i][j]=0; else dist[i][j]=mp[i][j]=INT_MAX; } int main() { int m,n; while(~scanf("%d %d",&m,&n)){ intt(); int ans=INT_MAX; for(int i=0;i<n;i++){ int a,b,c; scanf("%d %d %d",&a,&b,&c); if(mp[a-1][b-1]>c) mp[a-1][b-1]=dist[a-1][b-1]=c; if(mp[b-1][a-1]>c) mp[b-1][a-1]=dist[b-1][a-1]=c; } // for(int i=0;i<m;i++){ // for(int j=0;j<m;j++){ // printf("%d ",mp[i][j]); // } // printf(" "); // } for(int k=0;k<m;k++){ for(int i=0;i<k;i++){ for(int j=i+1;j<k;j++){ //printf("++%d %d %d ---%d ---%d %d %d ",mp[i][k],mp[j][k],mp[i][j],ans,i,j,k); ans=min(ans,(dist[i][k]+dist[j][k]+mp[i][j])); } } // for(int i=0;i<m;i++){ // for(int j=0;j<m;j++){ // printf("%d ",mp[i][j]); // } // printf(" "); // } for(int i=0;i<m;i++){ for(int j=0;j<m;j++){ //if(i==j) continue; mp[i][j]=min(mp[i][j],mp[i][k]+mp[j][k]); } } } // for(int i=0;i<m;i++){ // for(int j=0;j<m;j++){ // printf("%d ",mp[i][j]); // } // printf(" "); // } // for(int i=0;i<m;i++){ // if(mp[i][i]!=INT_MAX){ // //if(ans==-1) ans=mp[i][i]; // else ans=min(ans,mp[i][i]); // } // } if(ans!=INT_MAX) printf("%d ",ans); else printf("It's impossible. "); } return 0; }