描述 Description
Farmer John 打算将电话线引到自己的农场，但电信公司并不打算为他提供免费服务。于是，FJ 必须为此向电信公司支付一定的费用。 FJ 的农场周围分布着 N(1 <= N <= 1,000)根按 1..N 顺次编号的废弃的电话线杆，任意两根电话线杆间都没有电话线相连。一共 P(1 <= P <= 10,000)对电话线杆间可以拉电话线，其余的那些由于隔得太远而无法被连接。 第 i 对电话线杆的两个端点分别为 A_i、B_i，它们间的距离为 L_i (1 <= L_i <= 1,000,000)。数据中保证每对 {A_i，B_i} 最多只出现 1 次。编号为 1 的电话线杆已经接入了全国的电话网络，整个农场的电话线全都连到了编号为 N 的电话线杆上。也就是说，FJ 的任务仅仅是找一条将 1 号和 N 号电话线杆连起来的路径，其余的电话线杆并不一定要连入电话网络。 经过谈判，电信公司最终同意免费为 FJ 连结 K(0 <= K < N)对由 FJ 指定的电话线杆。对于此外的那些电话线，FJ 需要为它们付的费用，等于其中最长的电话线的长度（每根电话线仅连结一对电话线杆）。如果需要连结的电话线杆不超过 K 对，那么 FJ 的总支出为 0。 请你计算一下，FJ 最少需要在电话线上花多少钱。
输入格式 InputFormat
第 1 行: 3 个用空格隔开的整数：N，P，以及 K。
第 2..P+1 行: 第 i+1 行为 3 个用空格隔开的整数：A_i，B_i，L_i。
输出格式 OutputFormat
第 1 行: 输出 1 个整数，为 FJ 在这项工程上的最小支出。如果任务不可能完成， 输出 - 1
样例输入 SampleInput
30 50 2
29 20 46
17 28 95
27 18 30
27 6 39
6 20 30
26 14 47
26 3 92
10 2 80
18 6 35
12 23 8
17 21 47
23 29 36
23 17 55
23 13 5
22 10 20
11 5 80
14 30 65
3 2 88
30 19 61
27 22 56
24 8 38
18 28 100
4 12 35
8 1 47
17 2 40
13 17 32
5 26 16
29 16 30
26 7 24
11 6 13
3 28 13
30 12 62
11 18 58
24 5 5
6 13 21
2 8 88
7 6 18
14 19 48
5 18 83
8 15 45
29 27 59
10 6 16
13 27 72
9 18 87
26 21 95
3 18 6
8 6 54
13 7 88
12 13 25
10 1 35
样例输出 SampleOutput
21
数据范围和注释 Hint
一共有 5 根废弃的电话线杆。电话线杆 1 不能直接与电话线杆 4、5 相连。电话线杆 5 不能直接与电话线杆 1、3 相连。其余所有电话线杆间均可拉电话线。电信公司可以免费为 FJ 连结一对电话线杆。FJ 选择如下的连结方案：1->3；3->2；2->5，这 3 对电话线杆间需要的电话线的长度分别为 4、3、9。FJ 让电信公司提供那条长度为 9 的电话线，于是，他所需要购买的电话线的最大长度为 4。
来源 Source
Silver
代码 Code
二分答案，spfa 判断是否可行。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define inf 0x7fffffff/27.11
struct side
{
int z,y,x,next;
}a[20005];
int head[1001];
int f[1000000];
int dis[1001];
bool b[1001];
int i,j,t,n,m,l,r,k,p,q,ans;
bool spfa(int s)
{
int i,j,t,l,r,q;
memset(b,false,sizeof(b));
for (i=0;i<=n;i++) dis[i]=inf;
l=0;r=l;f[l]=1;dis[f[l]]=0;b[f[l]]=true;
while (r>=l)
{
t=f[l];
for (i=head[t];i!=0;i=a[i].next)
{
q=(a[i].z>s);
if (dis[a[i].y]>dis[t]+q)
{
dis[a[i].y]=dis[t]+q;
if (b[a[i].y]==false)
{
b[a[i].y]=true;
f[++r]=a[i].y;
}
}
}
b[t]=false;
l++;
}
return (dis[n]<=k);
}
int main()
{
memset(head,0,sizeof(head));
scanf("%d%d%d",&n,&p,&k);
m=0;
for (i=1;i<=p;i++)
{
scanf("%d%d%d",&l,&r,&q);
a[++m].x=l;a[m].y=r;a[m].z=q;a[m].next=head[l];head[l]=m;
a[++m].x=r;a[m].y=l;a[m].z=q;a[m].next=head[r];head[r]=m;
}
ans=inf;
l=0;r=2000000;
while (r>l)
{
t=(l+r)>>1;
if (spfa(t)) ans=min(ans,t),r=t;
else l=t+1;
}
if (ans>=1000000) printf("-1\n");
else printf("%d\n",ans);
return 0;
}