bfs，20pts，求助赏关（2） 20pts

#include<bits/stdc++.h>
//#include<windows.h>
using namespace std;
int h[10001] = {0},ck[10001] = {0},vis[10001] = {0};
int x,y,z,k,rpplus;
int cnt = 1;
struct bian{
    int end,next,w;
}a[100001];
int n,m;
bool specialcheck(){
	//cout<<"\nFor "<<num<<" now !"<<endl;
	for(int i = 1;i<=n;i++)vis[i] = 0;
	queue<int>c;
	int opl = -1;
	ck[1] = 0;
	ck[n] = -1;
	c.push(1);
	while(!c.empty()){
		int u = c.front();
		//cout<<"OOPS!"<<c.front()<<endl<<endl;
		//cout<<"try:"<<u<<endl;
		//Sleep(50);
		if(u==n or u==opl){
			vis[u] = (u==n);
			break;
		}
//		if(vis[u]==1){
//			cout<<"Err:"<<u<<" haved"<<endl;
	//		continue;
	//	}
		//printf("Now is %d ckfor %d.\n",u,ck[u]);
		//Sleep(50);
		int noweg = h[u];
        while(noweg!=0){
			//cout<<"finding edge from "<<u<<" to "<<a[noweg].end<<endl;
			if(vis[a[noweg].end]==0){
				ck[a[noweg].end] = ck[u]+1;
				c.push(a[noweg].end);
			}
            noweg = a[noweg].next;
        }
        //cout<<"Nicely Done."<<endl<<endl;
        vis[u] = 1;
        opl = u;
        c.pop();
	}
	//cout<<"All kill now."<<endl;

	if(vis[n]==0 or ck[n]>k)return false;
	return true;
}
bool check(int num){
	//cout<<"\nFor "<<num<<" now !"<<endl;
	for(int i = 1;i<=n;i++)vis[i] = 0;
	queue<int>c;
	int opl = -1;
	ck[1] = 0;
	ck[n] = -1;
	c.push(1);
	while(!c.empty()){
		int u = c.front();
		//cout<<"OOPS!"<<c.front()<<endl<<endl;
		//cout<<"try:"<<u<<endl;
		//Sleep(50);
		if(u==n or u==opl){
			vis[u] = (u==n);
			break;
		}
//		if(vis[u]==1){
//			cout<<"Err:"<<u<<" haved"<<endl;
	//		continue;
	//	}
		//printf("Now is %d ckfor %d.\n",u,ck[u]);
		//Sleep(50);
		int noweg = h[u];
        while(noweg!=0){
			//cout<<"finding edge from "<<u<<" to "<<a[noweg].end<<endl;
			if(vis[a[noweg].end]==0){
				//cout<<"OK."<<endl;
				if(a[noweg].w>num)ck[a[noweg].end] = ck[u]+1;
				else ck[a[noweg].end] = ck[u];
				if(ck[a[noweg].end]<=k)c.push(a[noweg].end);
			}
            noweg = a[noweg].next;
        }
        //cout<<"Nicely Done."<<endl<<endl;
        vis[u] = 1;
        opl = u;
        c.pop();
	}
	//cout<<"All kill now."<<endl;
	if(ck[n]>k)return false;// or ck[n]>k
	if(vis[n]==0)return false;
	return true;
}
void add(int u,int v,int we){
    a[cnt].end = v;
    a[cnt].next = h[u];
    a[cnt].w = we;
    h[u] = cnt;
    cnt++;
}
void print(){
    for(int i = 1;i<=n;i++){
        int noweg = h[i];
        cout<<i<<"    (headnum:"<<h[i]<<")";
        while(noweg!=0){
            cout<<i<<"to"<<a[noweg].end<<" for "<<a[noweg].w<<"  ";
            noweg = a[noweg].next;
        }
        cout<<endl;
    }
}
int main(){
	freopen("P1948_2.in","r",stdin);
	int ma = -1;
    cin>>n>>m>>k;
    for(int i = 1;i<=m;i++){
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);
        ma = max(ma,z);
    }
    //print();
    if(specialcheck()){
		cout<<0<<endl;
		return 0;
    }
    int l = 0,r = ma,mid,ans;
    while(l<r){
    	mid = (l+r)/2;
        if(check(mid)){
			r = mid;
			ans = mid;
		}
        else l = mid+1;
    }
    cout<<ans<<endl;
    return 0;
}