【信号连接】

题目描述

Nico 有一个排练室,她想把新买回来的 IMAX 银幕和放映机与远处的信号连接上,以便排练时可观看 lovelive 直播表演。

已知有 N 个信号发射仪,但其中只有 P 条线路能直接连接(Ai,Bi)(70%数据保证(A,B)只出现一次),且每条线路所花费的钱的就是该线路的长度 Li。保证源信号在 1 号点,排练室在 N 号点,且保证 1 和 N 不存在边。

现在要连通(1,N),工作人员答应帮忙免费连接原 P 条线路中的K条线路(可任选),若连上选择的 K 对后还无法连通(1,N),剩下连接中则需要 nico 为最长的线路(即最大边)付费。Nico 希望少花一点钱,所以请你帮帮她。

输入格式

多组数据(保证标程不超时)。
第 1 行:三个整数:N,P,K
第 2~P+1 行:每行三个整数 Ai,Bi,Li 。

输出格式

只有一行,输出 nico 所需花费的最少连接费用。
如果无法连接 1 和 N ,输出“-1”,不含引号。

样例数据 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

备注

对于 30% 的数据:n<=100;p<=1000
对于 100% 的数据: n<=1000;p<=10000;0<=k<n;0<a,b<=n,
对于(a,b),70% 数据保证每对只出现一次。

二分答案,分最大边,然后对所有边判断一下看那些边需要被付费,需要就把边权变1,否则变0,再跑一边SPFA即可,如果付费边<=k说明最大边还可以减小,否则增大,即可注意多组数据,数组要初始化!

下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*