比赛场次 105
比赛名称 20091026
比赛状态 已结束比赛成绩
开始时间 2011-10-26 19:00:00
结束时间 2011-10-26 22:00:00
开放分组 全部用户
注释介绍
题目名称 电话网络
输入输出 phone.in/out
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
GravatarTruth.Cirno AAATTTTTTT 0.000 s 0.00 MiB 30
GravatarYeehok WWAWWWWWWW 0.000 s 0.00 MiB 10
Gravatar11111111 WWAWWWWWWW 0.000 s 0.00 MiB 10
Gravatar风华正茂 WWAWWWWWWW 0.000 s 0.00 MiB 10
GravatarMakazeu WWAWWWWWWW 0.000 s 0.00 MiB 10
Gravatar临轩听雨ゐ WWWWWWWWWW 0.000 s 0.00 MiB 0
GravatarCloud WWWWWWWWWW 0.000 s 0.00 MiB 0
Gravatar日光。 WWWWWWWWWW 0.000 s 0.00 MiB 0
Gravatarsong WWWWWWWWWW 0.000 s 0.00 MiB 0
Gravatar血之侍卫 WWWWWWWWWW 0.000 s 0.00 MiB 0

电话网络

★★☆   输入文件:phone.in   输出文件:phone.out   简单对比
时间限制:1 s   内存限制:128 MiB

【题目描述】

由于地震使得连接汶川县城的电话线全部损坏,假如你是负责将电话线接到震中汶川县城的负责人,汶川县城周围分布着 N ( 1 ≤ N ≤ 1000 )根按 1..N 顺次编号的废弃的电话线杆去,任意两根电话线杆间都没有电话线相连。一共 P(1 ≤ P ≤ 10000) 对电话线杆间可以拉电话线,其余的由于地震使得无法被连接。

第 i 对电话线杆的两个端点分别为 Ai , Bi ,它们间的距离为 Li ( 1 ≤ Li ≤ 1000000 )。数据保证每对( Ai,Bi )最多只出现 1 次。编号为 1 的电话线杆已经接入了全国的电话网络,整个县城的电话线全都连到了编号为 N 的电话线杆上。也就是说,你的任务仅仅是找一条将 1 号和 N 号电话线杆连起来的路径,其余电话线杆并不一定要连入电话网络。

电信公司决定支援灾区免费为汶川县城连接 K ( 0 ≤ K < N )对由你指定的电话线杆。对于此外的那些电话线,需要为它们付费,总费用等于其中最长的电话线的长度(每根电话线仅连接一对电话线杆)。如果需要连接的电话线杆不超过 K 对,那么总支出为 0 。

请你计算一下,将电话线引到震中汶川县城最少需要在电话线上花多少钱?

【输入格式】

输入文件的第一行包含三个用空格隔开的整数: N,P 和 K 。

第二行到第 P+1 行:每行分别都为三个用空格隔开的整数: Ai,Bi 和 Li 。

【输出格式】

输出文件中仅包含一个整数,表示在这项工程上的最小支出。如果任务不可能完成,则输出- 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