1345: Strict k-th shortest path
题目
题目描述
给一个 $n (1\leq n \leq 10^5)$ 个点 $m(1\leq m\leq 2\times 10^5)$ 条边的有向图，求 $s$ 到 $t$ 的严格 $1, 2, \dots, k (k = 10)$ 短路的长度。
严格 $k$ 短路定义为：
-
$k = 1: $ 最短路。
-
$k > 1 :$ 严格长于 $k - 1$ 短路的路径中最短的一条。
在这里，路径上的点可重，这种路径在一些地方被称为途径 (walk)。
数据保证，$s$ 出发可以到达 $t$。
Input
请从 stdin 读入。
第一行为三个正整数 $n, m, s, t, k (k = 10)$。 第二行起 $m$ 行，每行三个非负整数 $u_i, v_i, w_i (0 \leq w_i \leq 10 ^ 9)$，表示从 $u_i$ 到 $v_i$ 有一条权值为 $w_i$ 的有向边。
Output
请输出到 stdout 中。
输出一行输出 $k$ 个整数，对于第 $i$ 个数，
- 如果存在严格 $i$ 短路，输出严格 $i$ 短路的长度。
- 否则，输出
-1。
如果你的所有测试点的前 $x$ 短路都答对了，且
- $x = 10$，
- 或存在 $x + 1$ 短路输出错误，
那么你将获得 $10x$ 分。
Sample Input
txt
2 3 1 2 10
1 2 1
1 2 1
1 2 2
txt
1 1 1 1 10
1 1 1
txt
5 4 1 5 10
1 2 1
2 3 1
3 4 1
4 5 1
Sample Output
txt
1 2 -1 -1 -1 -1 -1 -1 -1 -1
txt
0 1 2 3 4 5 6 7 8 9
txt
4 -1 -1 -1 -1 -1 -1 -1 -1 -1
Constraints
Time Limit: 1s
Memory Limit: 128MB
Oops! 本题目还没有解答！
助教老师们编题的速度，已经超过了解题的速度！
OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。
如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！