记录编号	546872	评测结果	AAAAAAAAAA
题目名称	电话网络	最终得分	100
用户昵称	云卷云书	是否通过	通过
代码语言	C++	运行时间	0.697 s
提交时间	2019-11-13 20:43:17	内存使用	3.31 MiB

#include<bits/stdc++.h>
using namespace std;
const int maxn=1007;
struct node{
	int to,w;
};
int d[maxn],vis[maxn];
vector<node> e[maxn],f[maxn];
int n,p,k,l=0,r,ans=-1;
deque<int> q;
void add(int a,int b,int c){
	node tmp;
	tmp.to=b,tmp.w=c;
	r=max(r,c);
	e[a].push_back(tmp);
}
bool check(int x){
	memset(d,0x3f,sizeof(d));
    memset(vis,0,sizeof(vis));
    deque<int> q;
    q.push_back(1);
    d[1]=0;
    vis[1]=1;
    while(!q.empty())
    {
        int a=q.front();
        q.pop_front();
        for(int i=0;i<e[a].size();i++)
        {
            int y=e[a][i].to;
            int b=e[a][i].w;
            if(!vis[y]||d[y]>=d[a]+1)
            if(b<=x)
            {
                vis[y]=1;
                q.push_front(y);
                d[y]=d[a];
            }
            else
            {
                vis[y]=1;
                q.push_back(y);
                d[y]=d[a]+1;
            }
        }
    }
    if(d[n]>k)
    return 0;
    else
    return 1;
}
int main(){
	freopen("phone.in","r",stdin);
	freopen("phone.out","w",stdout);
	scanf("%d%d%d",&n,&p,&k);
	for(int i=1;i<=p;i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
		add(b,a,c);
	}
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid)) r=mid-1,ans=mid;
		else l=mid+1;
	}
	cout<<ans;
	return 0;
}