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
       
        #include
        
         #define maxn 2020#define maxm 50500#define inf 100000000struct edge{    int u,v;    int val,next;} e[2*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,-1,sizeof(last));    t = 0;    for (int i=1; 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,0,sizeof(vis));    for (int i=1; i<=n; i++) dis[i] = inf;    int head = 0, tail = 0;    que[++tail] = A;    vis[A] = 1;    dis[A] = 0;    while (head < tail)    {        int u = que[++head];        for (int j=last[u]; j!=-1; 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]==0)                {                    vis[v] = 1;                    que[++tail] = v;                }            }        }        vis[u] = 0;    }    if (dis[B] < inf) return dis[B];    return -1;}int solve(){    int res = -1;    int l = 1, r = 10000;    while (l <= r)//二分最大边    {        int mid = (l + r)/2;        build(mid);        int tmp = spfa();        if (tmp == -1) l = mid + 1;        else        {
      //当mid(即每段中的最大值)减少时，res进行更新            res = tmp;            r = mid - 1;        }    }    return res;}int main(){    while (scanf("%d%d%d%d",&n,&m,&A,&B)==4)    {        for (int i=1; i<=m; i++) scanf("%d%d%d",&seq[i].u,&seq[i].v,&seq[i].val);        int ans = solve();        printf("%d\n",ans);    }    return 0;}
        
       

 

Sample Output

90 30 15