题目描述 Description
由于地震使得连接汶川县城电话线全部损坏，假如你是负责将电话线接到震中汶川县城的负责人，汶川县城周围分布着N(1≤N≤1,000)根按 1..N 顺次编号的废弃的电话线杆，任意两根电话线杆间都没有电话线相连。一共P(1≤P≤10,000)对电话线杆间可以拉电话线，其余的由于地震使得无法被连接。
第i对电话线杆的两个端点分别为Ai，Bi，它们间的距离为Li(1≤Li≤1,000,000)。数据中保证每对(Ai，Bi)最多只出现1次。编号为1的电话线杆已经接人了全国的电话网络，整个县城的电话线全都连到了编号为N的电话线杆上。也就是说，你的任务仅仅是找一条将1号和N号电话线杆连起来的路径，其余的电话线杆并不一定要连人电话网络。
电信公司决定支援灾区免费为汶川县城连结K(0≤K<N)对由你指定的电话线杆。对于此外的那些电话线，需要为它们付费，总费用等于其中最长的电话线的长度(每根电话线仅连接一对电话线杆)。如果需要连接的电话线杆不超过K对，那么总支出为0。
请你计算一下，将电话线引到震中汶川县城最少需要在电话线上花多少钱?
输入描述 Input Description
输入文件的第一行包含三个用空格隔开的整数：N，P和K。
第二行到第P+1行：每行分别都为空格隔开的整数：Ai，Bi和Li。
输出描述 Output Description
输出文件中仅包含一个整数，表示在这项工程上的最小支出。如果任务不可能完成，则输出-1。
样例输入 Sample Input
5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6
样例输出 Sample Output
4
//dis数组表示有几条边超过枚举的这个长度
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define maxn 20010
using namespace std;
int n,m,k,num,f[maxn],head[maxn],dis[maxn];
struct node
{
int u,v,t,pre;
} e[maxn];
int init()
{
int x=0;
char s=getchar();
bool f=0;
while(s<'0'||s>'9')s=getchar();
while(s>='0'&&s<='9') x=x*10+s-'0',s=getchar();
return x;
}
void Add(int from,int to,int dis)
{
num++;
e[num].u=from;
e[num].v=to;
e[num].t=dis;
e[num].pre=head[from];
head[from]=num;
}
void SPFA(int s)
{
queue<int>q;
dis[1]=0;
f[1]=1;
q.push(1);
while(!q.empty())
{
int p=q.front();
q.pop();
f[p]=0;
for(int i=head[p]; i; i=e[i].pre)
{
int si;
if(e[i].t<=s)
si=0;
else
si=1;
if(dis[e[i].v]>dis[p]+si)
{
dis[e[i].v]=dis[p]+si;
if(f[e[i].v]==0)
{
q.push(e[i].v);
f[e[i].v]=1;
}
}
}
}
}
int main()
{
n=init();
m=init();
k=init();
int x,y,z;
for(int i=1; i<=m; i++)
{
x=init();
y=init();
z=init();
Add(x,y,z);
Add(y,x,z);
}
int l=0,r=1000020,ans=-1;
while(l<=r)
{
memset(f,0,sizeof(f));
memset(dis,127/3,sizeof(dis));
int mid=(l+r)/2;
SPFA(mid);
if(dis[n]<=k)
{
int my=dis[n];
ans=mid;
r=mid-1;
}
else
l=mid+1;
}
printf("%d ",ans);
return 0;
}