问题标题: 酷町堂：求推图论题

酷町堂的没有多少，其它OJ的有一些。

灾后重建 (100分)
题目描述
暴风雨又一次的袭击了A城，这一次不仅B大街的供电线路遭到了破坏，整个A城的供电系统都遭到了破坏，包括市政府在内的大部分政府机构也都由于停电而无法办公。A城电力公司接到任务，需要尽快的修复一条供电线路来为市政府供电，小A又一次被安排核算修复费用。幸运的是A市还有N根编号为1...N的电线杆可以使用，其中第N根电线杆是为市政府供电的，但是所有电线杆之间的电线都被破坏了，电力公司经过检查发现，这N根电线杆中有M对电线杆之间是可以架设电线的。其中第i对电线杆分别是U_i和V_i，他们之间的距离是D_i，数据保证每对(U_i, V_i)只出现一次。经过抢修，编号为1的电线杆已经架设了连接A市发电厂的线路，也就是说只要将1号到N号通过电线连通（可能会通过其他电线杆中转），就可以将电接入市政府了。

为了加快施工进度，市政府愿意为P对由小A指定的电线杆之间的电线架设提供费用。除这P对以外的电线，电力公司需要为他们付费，总费用为其中最长的电线的长度（每根电线仅连接一对电线杆）。如果需要连接的电线杆不超过P对，那么支出为0。

小A想知道建立一条从1号电线杆到市政府的供电线路至少需要花多少钱。

输入格式
输入文件名：build.in

第1行：3个空格分隔的整数N, M, P，分别表示电线杆的数量、有M对电线杆之间可以拉电线，市政府愿意为其中P根电线付费。

第2到M+1行：每行三个空格分隔的整数，其中第i行的3个整数U_i，V_i和D_i，表示电线杆U_i和电线杆V_i之间可以假设电线，两根电线杆之间的距离为D_i。

输出格式
输出文件名：build.out

1行：一个整数，表示要接通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
输出样例1：
4
输入样例2：
4 3 2
2 3 1
2 4 2
3 4 3
输出样例2：
-1
说明
【数据范围】

对于10%的数据：N = 2，P = 1,  1 <= M <= 5，1 <= D_i <= 1000 

对于100%的数据：1<= N <= 1000，1<=U_i, V_i <= N，1 <= M <= 10000，0 ≤ P < N，1<= D_i <= 1000000。

【样例说明】

样例1：

共有5根电线杆，有7对电线杆之间可以假设电线，市政府愿意为一根电线提供费用。

假设3根电线分别为1->3， 3->2，2->5，其中2->5的电线选择让市政府付费，那么电力公司只需要花费4元钱，这是所有方案中最低的。





【样例2】

由于无法在1号电线杆和其他任何电线杆之间架设电线，无论如何都无法都无法将电从1号电线杆传输到4号电线杆。



【耗时限制】1000ms 【内存限制】256MB

感觉这道题不错，已经AC，提示：二分+最短路

后续添加，刘明

刘景程在2020-08-13 16:46:50追加了内容

写好了可以发给我，然后我来帮你交

样例过了一般就是对的

刘景程在2020-08-13 16:51:12追加了内容

熬熬那道题的连接找到了

https://www.luogu.org/problem/P1948