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");
}
else
printf("%d\n",max);
}
}
return 0;
}