本文主要是介绍hdu1599find the mincost route，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意：
在一个图里面找至少有三条边的无向环的最短路径。如果不存在有三条边以上的无向环则输出"It's impossible.".
解题思路：
带环了，所以就采用floyd算法吧，因为其它几种都是适用于单源的。
先上图；
至少三条边以上，按照一般思路的话，既然是最短路径，那我们肯定是边越少越好。但是从上图就可以看出，这个观点是显然不成立的。如1--3--5--1这个环的路径就要比1--2--3--4--5--1这个环的路径要长。
我们发现这两个环的最后两个顶点都是5---1，那么我们可不可以先将1--2--3--4给先压缩成一条边呢？当然可以啊，现在研究的不就是最短路么，就是说求1---4的最短路径，我们就用dis[1][4]表示好了。插叙一句，这个图用矩阵mp[n][n]表示，求出了1到4的最短路径，然后这个环就变成了1--4--5--1了，当然这个环的路径也就是dis[1][4]+mp[4][5]+map[5][1].
所以我们就是要一边维护一个dis[i][j]数组，表示i到j的最短路径，一边更新一个最小值mini，在这里需要注意的是为了避免经过相同的点，应该在dis[i][j]将k加入更新之前就应该更新ans,只有这样才能完全避免点k被使用两次！
#include<stdio.h>
#define N 100
#define inf 0xfffffff
int ans;
int mp[N][N],dis[N][N];
inline int mmin(int a,int b){return a<b?a:b;
}
void initi(int n){int i,j;for(i=0;i<=n;i++)for(j=0;j<=n;j++)mp[i][j]=dis[i][j]=inf;ans=inf;
}
void floyd(int n){int i,j,k;for(k=1;k<=n;k++){for(i=1;i<k;i++)for(j=1+i;j<k;j++)ans=mmin(ans,(dis[i][j]+mp[j][k]+mp[k][i]));for(i=1;i<=n;i++)for(j=1;j<=n;j++){if(i!=j&&j!=k&&i!=k)//不能用j=i+1<k的方法，必须将dis[i][j]和dis[j][i]都更新dis[i][j]=mmin(dis[i][k]+dis[k][j],dis[i][j]);}}
}
int main()
{int i,j,n,m,temp;int a,b,c;while(scanf("%d%d",&n,&m)!=EOF){initi(n);for(i=1;i<=m;i++){scanf("%d%d%d",&a,&b,&c);if(c<mp[a][b]){mp[a][b]=mp[b][a]=dis[a][b]=dis[b][a]=c;}}floyd(n);if(ans==inf)printf("It's impossible.\n");else{printf("%d\n",ans);}}
}
这篇关于hdu1599find the mincost route的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
