对于二分出的答案x而言，验证答案等价于将所有边权>x的边赋成1，否则赋成0，然后判断从1到n的最短路是否<=K。

#include
     
      #include
      
       #include
       
        using namespace std;#define N 1001#define M 10001int n,m,K,Xs[M],Ys[M],Zs[M];int first[N],next[M<<1],v[M<<1],en;bool w[M<<1];void AddEdge(int U,int V,bool W){	v[++en]=V;	w[en]=W;	next[en]=first[U];	first[U]=en;}queue
        
         q;bool inq[N];int d[N];void spfa(){	memset(d,0x7f,sizeof(int)*(n+1)); d[1]=0; q.push(1); inq[1]=1;	while(!q.empty())	  {	  	int U=q.front();	  	for(int i=first[U];i;i=next[i])	  	  if(d[v[i]]>d[U]+w[i])	  	    {	  	      d[v[i]]=d[U]+w[i];	  	      if(!inq[v[i]]) {q.push(v[i]); inq[v[i]]=1;}	  	    }	  	q.pop(); inq[U]=0;	  }}bool check(int x){	en=0; memset(first,0,sizeof(int)*(n+1));	for(int i=1;i<=m;++i) {AddEdge(Xs[i],Ys[i],Zs[i]>x); AddEdge(Ys[i],Xs[i],Zs[i]>x);}	spfa();	return d[n]<=K;}int main(){	scanf("%d%d%d",&n,&m,&K);	for(int i=1;i<=m;++i) scanf("%d%d%d",&Xs[i],&Ys[i],&Zs[i]);	int l=0,r=1000001;	while(r>l)	  {	  	int mid=(l+r>>1);	  	if(check(mid)) r=mid;	  	else l=mid+1;	  }	printf("%d\n",l<=1000000?l:(-1));	return 0;}