记录编号	533868	评测结果	AAAAAAAAAAAAA
题目名称	[USACO Jan08] 架设电话线	最终得分	100
用户昵称	leon	是否通过	通过
代码语言	C++	运行时间	0.051 s
提交时间	2019-07-02 09:32:40	内存使用	14.01 MiB

    #include<bits/stdc++.h>
    using namespace std;
    #define maxn 10001
    #define High 1000001
    #define ll long long 
    struct edge{
    	int to,next,v;
    } Edge[20005];
    int n,p,k,cnt,h[maxn],dis[maxn],q[maxn];
    int u,v,w,l=0,r=High,mid,ans=-1;
    bool pd[maxn];
    void add(int u,int v,int w){
        Edge[++cnt].to=v;
        Edge[cnt].v=w;
        Edge[cnt].next=h[u];
        h[u]=cnt;
    }
    bool check(int x){
        memset(dis,0x7f7f7f,sizeof(dis));
        int t=0,w=1,i,now,s;
        dis[1]=0;q[t]=1;pd[1]=1;
        while(t!=w){
    		now=q[t];t++;
    	    if(t==1001)t=0;
    	    i=h[now];
    	        while(i){
    	            if(Edge[i].v>x)s=dis[now]+1;
    	            else s=dis[now];
    	            if(s<dis[Edge[i].to]){
                        dis[Edge[i].to]=s;
                        if(!pd[Edge[i].to]){
                            q[w++]=Edge[i].to;
                            pd[Edge[i].to]=1;
                            if(w==1001)w=0;
                        }
    	            }
    	            i=Edge[i].next;
    	        }
    	        pd[now]=0;
        }
         if(dis[n]<=k) return 1;
         return 0;
     }
    int main()
    {
    	freopen("phoneline.in","r",stdin);
    	freopen("phoneline.out","w",stdout);
        scanf("%d%d%d",&n,&p,&k);
        for(int i=1;i<=p;i++){
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
            add(v,u,w);
        }
        while(l<=r){
            mid=(l+r)>>1;
            if(check(mid)){
    			r=mid-1;
    			ans=mid;
    		}
            else l=mid+1;
        }
        cout<<ans;
        return 0;
    }