导航切换
Back
Overview
Status
Standings
Printer
Login
Login
Register
Start:
Jun, 16, 2023 13:00:00
20230616二分查找+二分答案
End:
Jul, 16, 2023 17:00:00
Time elapsed:
Time remaining:
A
B
C
D
E
F
G
架设电线
1339
Time Limit:
1 Sec
Memory Limit:
256 MB
Submission：
8
AC：
1
Score：
100
Submit
Description
徐老师刚新建了一栋别墅，现在他要架设电线给别墅通电。
供电所的编号为 1，徐老师的别墅编号为 N，中间有 N-2 根电线杆，编号依次为 2 ...... N - 1。徐老师对于电量需求很大，需要通过电线杆架设私有电网。由于原先已经架设了很多电线，出于安全考虑，现在只有 P 对电线杆之间能架设电线（我们把供电所和别墅也当成一个电线杆），每一对包含两个电线杆 A_i 和 B_i，在 A_i 和 B_i 之间架设电线需要 L_i 米电线。
现在需要假设电线让供电所和徐老师的别墅能通电。徐老师依靠其强大的个人魅力，争取到让供电所免费帮他在 K 对电线杆直接架设电线，而剩下部分需要收费，收费标准为剩下的需要架设的电线的长度的最大长度。
帮忙计算一下，徐老师最少需要多少钱来架设电线。
Input
第一行输入 3 个整数 N(2 <= N <= 1000)，P(1 <= P <= 10000)，K(0 <= K < N)。
接下来输入 P 行，每行 3 个整数 A_i, B_i(1 <= A_i, B_i <= N)，L_i(1 <= L_i <= 10^6)，表示 A_i 和 B_i 之间能架设长度为 L_i 的电线。
Output
输出徐老师最少需要花费的钱数。如果徐老师的别墅不可能通电，输出 -1。
Samples
input:
5 7 1 1 2 5 3 1 4 2 4 8 3 2 3 5 2 9 3 4 7 4 5 6
output:
4
Submit