Description

Farmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of the cables required to connect his farm to the phone system.

There are N (1 ≤ N ≤ 1,000) forlorn telephone poles conveniently numbered 1…N that are scattered around Farmer John’s property; no cables connect any them. A total of P (1 ≤ P ≤ 10,000) pairs of poles can be connected by a cable; the rest are too far apart.

The i-th cable can connect the two distinct poles Ai and Bi, with length Li (1 ≤ Li ≤ 1,000,000) units if used. The input data set never names any {Ai, Bi} pair more than once. Pole 1 is already connected to the phone system, and pole N is at the farm. Poles 1 and N need to be connected by a path of cables; the rest of the poles might be used or might not be used.

As it turns out, the phone company is willing to provide Farmer John with K (0 ≤ K < N) lengths of cable for free. Beyond that he will have to pay a price equal to the length of the longest remaining cable he requires (each pair of poles is connected with a separate cable), or 0 if he does not need any additional cables.

Determine the minimum amount that Farmer John must pay.

翻译：

农夫约翰想在他的农场架设一条电话线。不幸的是，电话公司是不合作的，所以他需要支付一些电缆需要连接他的农场到电话系统。

有N（1≤N≤1000）个废弃的电线杆，方便地编号为1…N，散落在农夫约翰的房子里；没有电缆连接它们。共有P（1≤P≤10000）对电杆可用电缆连接，其余电杆相距太远。

第i根电缆可连接两个不同的极Ai和Bi，长度Li（1≤Li≤1000000）单位。输入数据没有重复的{Ai，Bi}对。1号杆已经连接到电话系统，N号杆在农场。极1和N需要通过电缆路径连接；其余的极可以使用也可以不使用。

事实证明，这家电话公司愿意免费为农民约翰提供K（0≤K<N）条电缆。除此之外，他将不得不支付相当于他所需的剩余最长电缆长度的价格（每对电线杆用单独的电缆连接），或者如果他不需要任何额外的电缆，则支付0。

请计算农夫约翰必须支付的最低金额。

Input
第1行：三个空格分隔的整数：N,P,和K
第2…P+1行：第i+1行包含三个空格分隔的整数：Ai、Bi和Li
Output
一个整数，农民约翰可以支付的最低金额。如果无法将农场连接到电话公司，请打印-1。

Sample Input

5 7 11 2 53 1 42 4 83 2 35 2 93 4 74 5 6

Sample Output

4

code

#include#define inf 0x3f3f3fusing namespace std;int n,m,k,c[10005],ans[1005];int head[1005],tot;int anss=0x3f3f;struct edge{int to,nxt,w;int b;}e[20005];void add(int x,int y,int z){e[++tot].to=y;e[tot].w=z;e[tot].nxt=head[x];head[x]=tot;}void dfs(int f,int x,int dep,int mid){if(dep>=ans[x]) return;ans[x]=dep;for(int i=head[x];i;i=e[i].nxt){int y=e[i].to;if(y==f) continue;if(e[i].w<=mid) dfs(x,y,dep,mid);else dfs(x,y,dep+1,mid);}}int main(){scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);c[i]=z;add(x,y,z);add(y,x,z);}sort(c+1,c+m+1);int l=0,r=m;while(l<r){int mid=c[(l+r)/2];memset(ans,inf,sizeof(ans));dfs(0,1,0,mid);if(ans[n]<=k){anss=mid;r=(l+r)/2;    }    else l=(l+r)/2+1;}if(anss==0x3f3f) printf("%d",-1);else printf("%d",anss);return 0;}

天天看天天赞！

我们明天再见，拜拜。

老江饲料商城