P1396 营救

/*

MST最小瓶颈生成树.

定理:MST中的最长边必定小于其他生成树中的最长边.

*/

#include<cstdio>

#include<iostream>

#include<algorithm>

#define MAXN 10001

using namespace std;

int n,m,father[MAXN],tot,ss,tt;

struct data

{

    int x,y,z;

}s[MAXN*2];

int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

    return x*f;

}

bool cmp(const data &x,const data &y)

{

    return x.z<y.z;

}

int find(int x)

{

    return x!=father[x]? father[x]=find(father[x]):x;

}

int main()

{

    n=read();m=read();ss=read();tt=read();

    for(int i=1;i<=n;i++) father[i]=i;

    for(int i=1;i<=m;i++)

      s[i].x=read(),s[i].y=read(),s[i].z=read();

    sort(s+1,s+m+1,cmp);

    for(int i=1;i<=m;i++)

    {

        int l1=find(s[i].x),l2=find(s[i].y);

        if(l1!=l2) tot++,father[l2]=l1;

        if(find(ss)==find(tt))

        {

            printf("%d",s[i].z);

            return 0;

        }

        if(tot==n-1) break;

    }

    return 0;

}

/*

二分拥挤值.

spfa大于拥挤值的边不选.

然后判能不能到达终点.

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#define MAXN 10001

using namespace std;

int n,m,s,t,head[MAXN],tot,dis[MAXN];

bool b[MAXN];

struct data

{

    int v,next,x;

}e[MAXN*4];

int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

    return x*f;

}

void add(int u,int v,int x)

{

    e[++tot].v=v;

    e[tot].x=x;

    e[tot].next=head[u];

    head[u]=tot;

}

bool spfa(int x)

{

    int q[MAXN*2]={0},head1=1,tail=0;

    memset(b,0,sizeof(b));

    memset(dis,127/3,sizeof(dis));dis[s]=0;q[++tail]=s;b[s]=true;

    while(head1<=tail)

    {

        int u=q[head1++];b[u]=false;

        for(int i=head[u];i;i=e[i].next)

        {

            int v=e[i].v;

            if(!b[v]&&e[i].x<=x&&dis[v]>dis[u]+e[i].x)

            {

                b[v]=true;

                dis[v]=dis[u]+e[i].x;

                q[++tail]=v;

            }

        }

    }

    if(dis[t]==dis[0]) return false;

    return true;

}

int erfen(int l,int r)

{

    int mid,ans=0;

    while(l<=r)

    {

        mid=(l+r)>>1;

        if(spfa(mid)) ans=mid,r=mid-1;

        else l=mid+1;

    }

    return ans;

}

int main()

{

    int x,y,z;

    n=read();m=read();s=read();t=read();

    for(int i=1;i<=m;i++)

    {

        x=read();y=read();z=read();

        add(x,y,z);add(y,x,z);

    }

    printf("%d",erfen(1,10000));

    return 0;

}