8206: [yosupo] Graph - K-Shortest Walk
[Creator : ]
Description
You are given a not necessarily simple directed graph with N vertices and M edges. The i-th edge is directed from vertex $a_i$ to vertex $b_i$ and has weight $c_i$.
For i from 1 to K (inclusive), output $x_i$, the length of the i-th shortest walk from vertex s to vertex t. If such walk doesn't exist, output -1.
Multiple walks with the same length are considered different walks.
For i from 1 to K (inclusive), output $x_i$, the length of the i-th shortest walk from vertex s to vertex t. If such walk doesn't exist, output -1.
Multiple walks with the same length are considered different walks.
Input
$N\ M\ s\ t\ K$
$a_0\ b_0\ c_0$
$a_1\ b_1\ c_1$
$⋮$
$a_{M−1}\ b_{M−1}\ c_{M−1}$
$a_0\ b_0\ c_0$
$a_1\ b_1\ c_1$
$⋮$
$a_{M−1}\ b_{M−1}\ c_{M−1}$
Output
$x_1$
$x_2$
$⋮$
$x_K$
$x_2$
$⋮$
$x_K$
Constraints
$1≤N,M≤300,000$
$1≤K≤300,000$
$0≤s,t<N$
$0≤u_i,v_i<N$
$0≤c_i≤10^7$
$1≤K≤300,000$
$0≤s,t<N$
$0≤u_i,v_i<N$
$0≤c_i≤10^7$
Sample 1 Input
4 5 0 3 5
0 1 1
1 2 1
2 3 1
0 2 1
1 3 1
Sample 1 Output
2
2
3
-1
-1