codevs 3336 电话网络

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define maxn 20010
using namespace std;
int n,m,k,num,f[maxn],head[maxn],dis[maxn];
struct node
{
    int u,v,t,pre;
}e[maxn];
int init()
{
    int x=0;char s=getchar();bool f=0;
    while(s<'0'||s>'9'){if(s=='-')f=1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    if(f)return -x;return x;
}
void Add(int from,int to,int dis)
{
    num++;
    e[num].u=from;
    e[num].v=to;
    e[num].t=dis;
    e[num].pre=head[from];
    head[from]=num;
}
void SPFA(int s)
{
    queue<int>q;
    dis[1]=0;
    f[1]=1;
    q.push(1);
    while(!q.empty())
      {
          int p=q.front();
          q.pop();
          f[p]=0;
          for(int i=head[p];i;i=e[i].pre)
            {
                int si;
                if(e[i].t<=s)si=0;else si=1;
                if(dis[e[i].v]>dis[p]+si)
                  {
                    dis[e[i].v]=dis[p]+si;
                if(f[e[i].v]==0)
                  {
                    q.push(e[i].v);
                    f[e[i].v]=1;
                  }
              }
          }
      }
}
int main()
{
    n=init();m=init();k=init();

    int x,y,z;
    for(int i=1;i<=m;i++)
      {
          x=init();y=init();z=init();
          Add(x,y,z);
          Add(y,x,z);
      }
    int l=0,r=1000020,ans=-1;
    while(l<=r)
      {
        memset(f,0,sizeof(f));
        memset(dis,127/3,sizeof(dis));
          int mid=(l+r)/2;
          SPFA(mid);
        if(dis[n]<=k)
            {
                ans=mid;
                r=mid-1;
          }
        else l=mid+1;
      }
    printf("%d
",ans);
    return 0;
}