记录编号	120979	评测结果	AAAAAAAAAA
题目名称	电话网络	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.671 s
提交时间	2014-09-17 16:03:08	内存使用	7.98 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>

#define Maxn 1002
#define INF 1000001

using namespace std;

int n,p,G[Maxn][Maxn]={0};
int R[Maxn][Maxn]={0},dis[Maxn];
bool u[Maxn]={0};

int dijstra(int x){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j) continue;
			if(G[i][j]==0) R[i][j]=-INF;
			else if(G[i][j]<=x) R[i][j]=0;
			else R[i][j]=1;
		}
		dis[i]=INF;
		u[i]=0;
	}
	dis[1]=0;
	for(int i=2;i<=n;i++){
		int k=0;
		for(int j=1;j<=n;j++){
			if(!u[j] && dis[j]<dis[k]) k=j;
		}
		u[k]=true;
		for(int j=1;j<=n;j++){
			if(G[k][j]!=0 && dis[j]>dis[k]+R[k][j]){
				dis[j]=dis[k]+R[k][j];
			}
		}
	}
	return dis[n];
}

void init(){
	int x,y,z,k;
	cin>>n>>p>>k;
	for(int i=1;i<=p;i++){
		cin>>x>>y>>z;
		G[x][y]=max(G[x][y],z);
		G[y][x]=max(G[y][x],z);
	}
	dis[0]=INF+1;
	int l=0,r=INF;
	while(l<=r){
		int mid=(l+r)>>1;
		if(dijstra(mid)<=k) r=mid-1;
		else l=mid+1;
	}
	if(l>=INF) cout<<-1<<endl;
	else cout<<l<<endl;
}

int main(){
	freopen("phone.in","r",stdin);
	freopen("phone.out","w",stdout);
	init();
	return 0;
}