记录编号	541352	评测结果	AAAAAAAAAAAAA
题目名称	[USACO Jan08] 架设电话线	最终得分	100
用户昵称	ShallowDream雨梨	是否通过	通过
代码语言	C++	运行时间	0.221 s
提交时间	2019-09-09 08:49:41	内存使用	18.33 MiB

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=100005;
const int inf=2100000000;
ll now[maxn],tot,head[maxn],dis[maxn];
	ll n,m,k,q,w,e;//n_dian
bool vis[maxn];
struct road{int to,next,v;}a[maxn*2];
void add(int x,int y,int z){
	a[++tot].to=y;a[tot].v=z;
	a[tot].next=head[x];head[x]=tot;}
bool check(int x){
	typedef pair<ll,ll>p;
priority_queue<p,vector<p>,greater<p> >q;
	for(int i=1;i<=n;i++)vis[i]=0;
	for(int i=2;i<=n;i++)dis[i]=inf;
	for(int i=1;i<=tot;i++){
	if(a[i].v<=x)now[i]=0;
	else now[i]=1;}
	q.push(p(0,1));
	while(!q.empty()){
	int qwq=q.top().second;q.pop();
	if(vis[qwq]==0){
		vis[qwq]=1;
	for(int i=head[qwq];i;i=a[i].next){
		if(dis[a[i].to]>dis[qwq]+now[i]){
			dis[a[i].to]=dis[qwq]+now[i];
			q.push(p(dis[a[i].to],a[i].to));}}}}
	if(dis[n]>k)return false;return true;}
int main(){
	freopen("phoneline.in","r",stdin);
		freopen("phoneline.out","w",stdout);
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++){
		cin>>q>>w>>e;
		add(q,w,e);add(w,q,e);}
	int l=0,r=10000000,ans=-1;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid)==false)
			l=mid+1;
			else r=mid-1,ans=mid;}
			cout<<ans;
	return 0;
}