Description
Alice想要从城市A出发到城市B,由于Alice最近比较穷(不像集训队陈兴老师是个rich second)，所以只能选择做火车从A到B。不过Alice很讨厌坐火车，火车上人比较多，比较拥挤，所以Alice有很严格的要求：火车的相邻两站间的最大距离尽可能的短，这样Alice就可以在停站的时候下车休息一下。当然Alice希望整个旅途比较短。
Input
有多组测试数据。
每组测试数据的第一行有两个整数N,M，A,B(N<=2000, M<=50000, N >=2, A,B<=N),其中N是城市的个数，M是城市间通火车的个数。
A,B是Alice起始的城市与目的地城市，城市的标号从1开始。
接下来的M行每行三个整数u,v，w表示从u到v和从v到u有一条铁路，距离为w， u,v<=N, w<=10000。
Output
对于每组测试数据输出满足Alice要求的从A到B的最短距离。
Sample Input
3 3 1 2
1 2 80
1 3 40
2 3 50
3 3 1 2
1 2 90
1 3 10
2 3 20
4 5 1 4
1 2 8
1 4 9
1 3 10
2 4 7
3 4 8
#include<stdio.h>
#include<string.h>
#define maxn 2020
#define maxm 50500
#define inf 100000000 struct edge
{
int u,v;
int val,next;
} e[*maxm],seq[maxm]; int last[maxn];
int que[maxm],dis[maxn];
bool vis[maxn];
int t,n,m,A,B; void add(int u,int v,int val)//离散化存储
{
e[t].v = v;
e[t].val = val;
e[t].next = last[u];
last[u] = t++;
return ;
}
void build(int val)//建树
{
memset(last,-,sizeof(last));
t = ;
for (int i=; i<=m; i++)
if (seq[i].val <= val)
{
add(seq[i].u,seq[i].v,seq[i].val);
add(seq[i].v,seq[i].u,seq[i].val);
}
return ;
} int spfa()
{//采用负权存储
memset(vis,,sizeof(vis));
for (int i=; i<=n; i++) dis[i] = inf;
int head = , tail = ;
que[++tail] = A;
vis[A] = ;
dis[A] = ;
while (head < tail)
{
int u = que[++head];
for (int j=last[u]; j!=-; j=e[j].next)//遍历与j相连的边
{
int v = e[j].v;
int val = e[j].val;
if (dis[u] + val < dis[v]) //松弛条件判断
{
dis[v] = dis[u] + val;
if (vis[v]==)
{
vis[v] = ;
que[++tail] = v;
}
}
}
vis[u] = ;
}
if (dis[B] < inf) return dis[B];
return -;
}
int solve()
{
int res = -;
int l = , r = ;
while (l <= r)//二分最大边
{
int mid = (l + r)/;
build(mid);
int tmp = spfa();
if (tmp == -) l = mid + ;
else
{//当mid(即每段中的最大值)减少时，res进行更新
res = tmp;
r = mid - ;
}
}
return res;
}
int main()
{
while (scanf("%d%d%d%d",&n,&m,&A,&B)==)
{
for (int i=; i<=m; i++) scanf("%d%d%d",&seq[i].u,&seq[i].v,&seq[i].val);
int ans = solve();
printf("%d\n",ans);
}
return ;
}
图论（二分+SPFA）
Sample Output
90 30 15