记录编号	533078	评测结果	AAAAAAAAAAAAA
题目名称	[USACO Jan08] 架设电话线	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	1.144 s
提交时间	2019-06-14 12:38:15	内存使用	21.33 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("phoneline.in","r",stdin);
	freopen("phoneline.out","w",stdout);
	init();
	return 0;
}