| 题目名称 | 386. 电话网络 |
|---|---|
| 输入输出 | phone.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2009-10-26加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：81， 提交：161， 通过率：50.31% | ||||
 LGLJ |
100 | 0.003 s | 1.39 MiB | C++ |
 Fisher. |
100 | 0.018 s | 0.38 MiB | C++ |
 irony |
100 | 0.020 s | 0.37 MiB | C++ |
 rewine |
100 | 0.021 s | 0.58 MiB | C++ |
 Neptune |
100 | 0.022 s | 0.33 MiB | C++ |
|
irony |
100 | 0.022 s | 0.36 MiB | C++ |
 quifar |
100 | 0.025 s | 0.63 MiB | C++ |
 AAAAAAAAAA |
100 | 0.031 s | 0.66 MiB | C++ |
 f0rest |
100 | 0.033 s | 0.33 MiB | C++ |
 Fancy、 |
100 | 0.033 s | 0.60 MiB | C++ |
| 本题关联比赛 | |||
| 20091026 | |||
| 20091026 | |||
| 不准粘代码，必须自己写(HS除外) | |||
| 不准粘代码，必须自己写(HS除外) | |||
| 关于 电话网络 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
我是EE怪
| ||||
|
双倍经验见usaco架设电话线
 Magic_Sheep
2016-09-27 20:25
3楼
| ||||
|
受不了了,dijistra都不会打了,因为dis[0]的缘故调了半天。
| ||||
|
重题了。
 怡红公子
2012-10-30 01:18
1楼
| ||||
天一阁
【题目描述】
由于地震使得连接汶川县城的电话线全部损坏，假如你是负责将电话线接到震中汶川县城的负责人，汶川县城周围分布着 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