poj 3615 Cow Hurdle (Floyd)

题目链接：  http://poj.org/problem?id=3615

题目大意：  给出有N个顶点M条边的有向连通图

                    H可以抽象为每条路的长度

                    询问T次，每次询问的内容是：

                    A到B点能走的所有路中最长的那段路最短是多少？

解题思路：  最长的那段路最短是多少，可以用Floyd枚举每一条边

                    先加入的一个点k，判断 i---->k点 和 k点--->j点 的最大值

                    把最大值与直接从i--->j的长度对比，取最小那个

                    也就是说加入点k，有可能使得i到j点的最长那段路还要短

                    方程:  if(edge[i][j]>max(edge[i][k],edge[k][j]))   

                                      edge[i][j]=max(edge[i][k],edge[k][j]);

代码：

/* Floyd 变形题意:求从a到b的路程中最长的那段路最短方程: if(edge[i][j]>(max(edge[i][k],edge[k][j])))   edge[i][j]=(max(edge[i][k],edge[k][j]));错误地方: if(edge[i][j]>max(edge[i][k],edge[k][j]))  这样是错误的!!!!!
*/
#include 
#include 
#define MAX 301
#define INF 0x3f3f3f3f
#define max(a,b) (a>b)?a:b  //**新学的用法
int n,m,t,edge[MAX][MAX];int main()
{int i,j,a,b,k,h,temp;scanf("%d%d%d",&n,&m,&t);memset(edge,INF,sizeof(edge));for(i=1;i<=m;i++) {scanf("%d%d%d",&a,&b,&h);edge[a][b]=h;}for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++){temp=max(edge[i][k],edge[k][j]);  //下次都用temp了，不然会错误if(edge[i][j]>temp)  //**关键点{edge[i][j]=temp;}}for(i=1;i<=t;i++){scanf("%d%d",&a,&b);if(edge[a][b]!=INF){printf("%d\n",edge[a][b]);}else{printf("-1\n");}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！