Skip to content

1196: 架设电话线

题目

题目描述

FarmerJohn打算将电话线引到自己的农场,但电信公司并不打算为他提供免费服务。于是,FJ必须为此向电信公司支付一定的费用。FJ的农场周围分布着$N$根按$1\cdots N$顺次编号的废弃的电话线杆,任意两根电话线杆间都没有电话线相连。一共$P$对电话线杆间可以拉电话线,其余的那些由于隔得太远而无法被连接。

第$i$对电话线杆的两个端点分别为$A_i,B_i$,它们间的距离为$L_i$。数据中保证每对$(A_i,B_i)$最多只出现一次。编号为$1$的电话线杆已经接入了全国的电话网络,整个农场的电话线全都连到了编号为$N$的电话线杆上。也就是说,FJ的任务仅仅是找一条将$1$号和$N$号电话线杆连起来的路径,其余的电话线杆并不一定要连入电话网络。经过谈判,电信公司最终同意免费为FJ连结$K$对由FJ指定的电话线杆。对于此外的那些电话线,FJ需要为它们付的费用,等于其中最长的电话线的长度(每根电话线仅连结一对电话线杆)。如果需要连结的电话线杆不超过$K$对,那么FJ的总支出为$0$。请你计算一下,FJ最少需要在电话线上花多少钱。

输入格式

第一行: 三个用空格隔开的整数:$N,P,K$

第$2\cdots P+1$行: 第$i+1$行为三个用空格隔开的整数:$A_i,B_i,L_i$

输出格式

输出一行一个整数,表示最少花费。

如果不可能完成,输出$-1$。

样例输入

5 7 1

1 2 5

3 1 4

2 4 8

3 2 3

5 2 9

3 4 7

4 5 6

样例输出

4

提示

FJ选择如下的连结方案:$1->3;3->2;2->5$,这三对电话线杆间需要的电话线的长度分别为$4、3、9$。FJ让电信公司提供那条长度为$9$的电话线,于是,他所需要购买的电话线的最大长度为$4$。

数据范围

对于 $100\%$的数据,$1\le N \le 1000,1 \le P \le 10000,1\le L_i \le 1000000,0\le K< N$。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!