本文主要是介绍HDU 1595——find the longest of the shortest，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
dijcstra算法
做法是在这个无向图中，先求出起点到终点的最短路径，并且标记出起点到终点所经过的节点，然后在采用枚举法，把其中的道路改变。求出其中的最大值即可。
代码写的很难看，懒得改了。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define INF 100001
int map[1003][1003],dis[1003],be[1003];//be[i]代表i点的前一个点
bool que[1003];
int main()
{int n,m,min,k,i,j;int s,e,t;while(scanf("%d%d",&n,&m)!=EOF){memset(que,0,sizeof(que));for(i=1;i<=n;i++)for(j=1;j<=n;j++)map[i][j]=INF;for(i=1;i<=m;i++){scanf("%d%d%d",&s,&e,&t);if(map[s][e]>t)map[s][e]=map[e][s]=t;}for(i=1;i<=n;i++){dis[i]=map[1][i];be[i]=1;}que[1]=1;dis[1]=0;for(i=2;i<=n;i++){min=INF;for(j=1;j<=n;j++)if(!que[j]&&dis[j]<min){min=dis[j];k=j;}que[k]=1;if(min==INF||que[n]){break;}for(j=1;j<=n;j++)if(!que[j]&&dis[j]>map[k][j]+dis[k]){dis[j]=map[k][j]+dis[k];be[j]=k;}}if(dis[n]==INF){printf("-1\n");}else{int num,S,E,T;int max;max=dis[n];num=n;while(num!=1){S=num;E=be[num];T=map[num][be[num]];map[S][E]=map[E][S]=INF;memset(que,0,sizeof(que));for(i=1;i<=n;i++)dis[i]=map[1][i];que[1]=1;dis[1]=0;for(i=2;i<=n;i++){min=INF;for(j=1;j<=n;j++)if(!que[j]&&dis[j]<min){min=dis[j];k=j;}que[k]=1;if(min==INF||que[n]){break;}for(j=1;j<=n;j++)if(!que[j]&&dis[j]>map[k][j]+dis[k])dis[j]=map[k][j]+dis[k]; }if(max<dis[n])max=dis[n];map[S][E]=map[E][S]=T;num=be[num];}if(dis[n]==INF){printf("-1\n");}elseprintf("%d\n",max);}}return 0;
}
这篇关于HDU 1595——find the longest of the shortest的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
