| 题目名称 | 1950. KZ菌的星际旅行 |
|---|---|
| 输入输出 | KZstartravelillu.in/out |
| 难度等级 | ★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 KZNS
于2015-04-24加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：44， 提交：82， 通过率：53.66% | ||||
 LCWhiStLe |
100 | 0.005 s | 6.36 MiB | C++ |
 安呐一条小咸鱼。 |
100 | 0.039 s | 1.28 MiB | C++ |
 森林 |
100 | 0.053 s | 1.54 MiB | C++ |
|
森林 |
100 | 0.055 s | 1.18 MiB | C++ |
|
森林 |
100 | 0.057 s | 3.02 MiB | C++ |
|
森林 |
100 | 0.078 s | 1.45 MiB | C++ |
|
森林 |
100 | 0.078 s | 1.54 MiB | C++ |
 Hzoi_chairman |
100 | 0.086 s | 1.35 MiB | C++ |
 wolf |
100 | 0.092 s | 0.31 MiB | C++ |
|
wolf. |
100 | 0.094 s | 0.31 MiB | C++ |
| 本题关联比赛 | |||
| 欢乐水题赛 | |||
| 关于 KZ菌的星际旅行 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
MMMMMMMMMM
  小e
2016-08-29 16:38
8楼
| ||||
|
100W条边足矣。出题人吓唬人说1000W
（据说邻接表10W就能过） | ||||
|
| ||||
|
SPFA写挂了。。
 liu_runda
2016-05-08 06:57
5楼
| ||||
|
我还正反来一遍 。。。。。本来乘二就行了 分析一下是我把2吃了
 <蒟蒻>我要喝豆奶
2015-08-02 18:52
4楼
| ||||
|
我还正反来一遍 。。。。。本来乘二就行了 分析一下是我把2吃了
<蒟蒻>我要喝豆奶
2015-08-02 18:52
3楼
| ||||
|
大家好好读题呀~~~~不要担心数据范围！！
PS：Wolf。。。。  KZNS
2015-04-24 20:27
2楼
| ||||
|
警告
这个KZ菌出的题有些坑。 我在这里提供思路和坑点： 首先是个最短路问题； 其次是个无向图问题 再其次N不代表节点的最大编号 （节点编号最大能达到1’000‘001） PS:题目里KZ菌调皮的写了 10,000,001这个鬼数字 因为他觉得七个零很吉利 （vector党要注意了，比如我） 最后这个题是算双程路径，所以要乘二 （KZ菌的样例就是让你们看不到这点） | ||||
kito
哒哒哒哒哒！【题目描述】
Once upon a time.
KZ菌十分的无聊，他打算去某星球上去玩，没错，地球已经满足不了KZ菌了。KZ菌现在在1号星球——也就是地球。
KZ菌表示火箭实在太慢了，不过幸好科技早已发展到有星际旅行机器的存在，它们可以在近乎瞬间把KZ菌变成能量，然后送到远方，不过这些空间机器只能到达与之关联的另一台机器。当然，星际旅游局一定会去收KZ菌的钱的，因为他们还是需要赚钱什么的。不过还是有某些好心的企业，他们提供的有免费的空间机器。
KZ菌作为一个并不富有的团子状外星人，自然不会自己去算如何才能更省钱，所以他把这个任务交给了他的助手——Illu酱，不过Illu酱作为一个高端的AI，她是相当不愿意做这么简单的问题，于是她把问题挂在了过去的网上。
【输入格式】
输入共有M+1行：
第1行有2个数 N M：
表示KZ菌想去的星球编号N和现在已经被制造出M对星际旅行机器。
第2->M+1行中各有3个数a b s：
表示某对空间机器被放在了编号为a和b的星球上，用这对空间机器星际旅游局会收KZ菌s元RMB。
【输出格式】
输出共有1行：
第1行有1个数：
表示KZ菌来回要花的RMB。
【样例输入】
2 1 1 2 0
【样例输出】
0
【提示】
不会有人用负数、零、小数、无理数或虚数来为星球编号。
有关部门并没有发现第10,000,001号星球。
有关部门不会倒贴钱。
没有10,000,000以上对空间机器。
KZ菌没有2147483647RMB，但他一定可以到达他想去的星球。
表示KZ菌没有自己造空间机器的能力。
表示Illu酱可以变成电磁波来移动，所以不需要用空间机器。
第一个测试点一定是样例
PS：你的代码再好KZ菌也不会带你一起去的。
PPS：向KZNS@foxmail.com反馈。
【来源】
KZ's UBWH.