YGOI_真神名曰驴蛋蛋
Hzoi_有n个城市和m条单向道路，城市编号为1~n。每条道路连接两个不同的城市，且任意两条道路要么起点不同要么终点不同，因此n和m满足m<=n(n-1)。给定两个城市a和b，可以给a到b的所有简单路（所有城市最多经过一次，包括起点和终点）排序：先按长度从小到大排序，长度相同时按照字典序从小到大排序。你的任务是求出a到b的第k短路。
| 题目名称 | 2342. [SCOI 2007]kshort |
|---|---|
| 输入输出 | bzoj_1073.in/out |
| 难度等级 | ★★★★ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 512 MiB |
| 测试数据 | 10 |
| 题目来源 |
 YGOI_真神名曰驴蛋蛋
于2016-06-14加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：31， 提交：168， 通过率：18.45% | ||||
 liumy |
100 | 0.113 s | 0.43 MiB | C++ |
 sssSSSay |
100 | 0.134 s | 0.50 MiB | C++ |
|
sssSSSay |
100 | 0.139 s | 0.47 MiB | C++ |
|
sssSSSay |
100 | 0.142 s | 0.50 MiB | C++ |
 dsl2002 |
100 | 0.168 s | 496.47 MiB | C++ |
 刷题王 |
100 | 0.194 s | 1.19 MiB | C++ |
 徐心雨 |
100 | 0.213 s | 0.35 MiB | C++ |
 rewine |
100 | 0.868 s | 2.99 MiB | C++ |
 MLE |
100 | 0.968 s | 0.54 MiB | C++ |
 onlysky |
100 | 0.993 s | 0.38 MiB | C++ |
| 关于 kshort 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @_Itachi :
哇好主意我居然没想到QWQ sssSSSay
2017-04-16 07:12
9楼
| ||||
|
回复 @sssSSSay :
把自己的账号删了做题记录就没了  _Itachi
2017-04-15 17:45
8楼
| ||||
|
回复 @sssSSSay :
蓝鹅并不能删除了233333333  Albert S. Chang
2017-04-15 15:46
7楼
| ||||
|
第六点打了表感觉好罪恶
怎么把自己的记录删掉在线等挺急的QWQ | ||||
|
除了“路人皆打表”的第6个点外，我第8个点也死活过不了，果然我太弱了，弃坑了
_Itachi
2017-02-22 06:33
5楼
| ||||
|
真的，我没有骗数据，真的，我就是在不停的改，但是它就是每次多过一个点，我有什么办法（耸肩）。
_Itachi
2017-02-21 21:42
4楼
| ||||
|
| ||||
|
回复 @CNO.140 苦厄兽 驴蛋蛋 :
【滑稽】  rvalue
2016-07-08 17:22
2楼
| ||||
【题目描述】
【输入格式】
输入第一行包含五个正整数n, m, k, a, b。以下m行每行三个整数u, v, l，表示从城市u到城市v有一条长度
为l的单向道路。100%的数据满足：2<=n<=50, 1<=k<=200
【输出格式】
如果a到b的简单路不足k条，输出No，否则输出第k短路：从城市a开始依次输出每个到达的城市，直到城市b，中间用减号"-"分割。
【样例输入】
【样例输入1】 5 20 10 1 5 1 2 1 1 3 2 1 4 1 1 5 3 2 1 1 2 3 1 2 4 2 2 5 2 3 1 1 3 2 2 3 4 1 3 5 1 4 1 1 4 2 1 4 3 1 4 5 2 5 1 1 5 2 1 5 3 1 5 4 1 【样例输入2】 4 6 1 1 4 2 4 2 1 3 2 1 2 1 1 4 3 2 3 1 3 4 1 【样例输入3】 3 3 5 1 3 1 2 1 2 3 1 1 3 1
【样例输出】
【样例输出1】 1-2-4-3-5 【样例输出2】 1-2-3-4 【样例输出3】 No
【提示】
第一个例子有5个城市，所有可能出现的道路均存在。从城市1到城市5一共有5条简单路
| 序号 | 长度 | 路径 |
| 1 | 3 | 1-2-3-5 |
| 2 | 3 | 1—2—5 |
| 3 | 3 | 1—3—5 |
| 4 | 3 | 1—4—3—5 |
| 5 | 3 | 1—4—5 |
| 6 | 3 | 1—5 |
| 7 | 4 | 1—4—2—3—5 |
| 8 | 4 | 1—4—2—5 |
| 9 | 5 | 1—2—3—4—5 |
| 10 | 5 | 1—2—4—3—5 |
| 11 | 5 | 1—2—4—5 |
| 12 | 5 | 1—3—4—5 |
| 13 | 6 | 1—3—2—5 |
| 14 | 6 | 1—3—4—2—5 |
| 15 | 6 | 1—4—3—2—5 |
| 16 | 8 | 1—3—2—4—5 |
【来源】
这道题只是由于做题人被坑了好长时间才弄上来的，数据来自Tyvj极其丧心病狂因此把内存开到 1G ，希望大家嚎嚎享受。
然而事实证明即使内存开到1G也还是过不了第⑥个点，希望能看到不打表的 袋马 。_(:з」∠)_