Skip to content

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了,可以的话,请您参考添加页面,与大家一起分享你的题解!