记录编号	429965	评测结果	AAAAAAAAAA
题目名称	电话网络	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	0.018 s
提交时间	2017-07-28 23:25:40	内存使用	0.38 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f; 
}
const int maxn=1010;
const int maxm=10010;
int n,m,k;
queue<int>duilie;
int d[maxn];
bool ok[maxn];
vector<int>g[maxn];
vector<int>w[maxn];
int f[maxm];
inline bool spfa(int guess){//很妙的用法！ 
	memset(d,0x3f3f3f3f,sizeof(d));
	d[1]=0;
	ok[1]=1;
	duilie.push(1);
	while(!duilie.empty()){
		int u=duilie.front();duilie.pop();
		for(int i=0;i<g[u].size();i++){
			int v=g[u][i];
			int sue=w[u][i]<=guess?0:1;//<= 
			if(d[v]>d[u]+sue){
				d[v]=d[u]+sue;
				if(!ok[v]){
					ok[v]=1;
					duilie.push(v);	
				}
			}
		}
		ok[u]=0;
	} 
	if(d[n]>k)return 0;
	else return 1;
}
inline void erfen(){
	int l=0,r=m;
	while(l<r){
		int m=(l+r)>>1;
		if(spfa(f[m]))r=m;
		else l=m+1;
	}
	printf("%d\n",f[l]);
}
int main(){
	freopen("phone.in","r",stdin);
	freopen("phone.out","w",stdout);
	n=read();m=read();k=read();
	for(int i=1;i<=m;i++){
		int x=read(),y=read(),v=read();
		g[x].push_back(y);
		w[x].push_back(v);
		g[y].push_back(x);
		w[y].push_back(v); 
		f[i]=v;
	}
	sort(f+1,f+m+1);
	if(!spfa(f[m]))
		puts("-1");
	else
		erfen();
	return 0;
}