K-Shortest Walk

AC一覧

Problem Statement
問題文

頂点数 $N$、辺数 $M$ の単純とは限らないグラフが与えられる。$i$番目の辺は頂点$a_i$から$b_i$にはられており、重さ$c_i$である。

頂点$s$から頂点$t$への$1$番目から$K$番目に短いウォークの長さ$x_i$をそれぞれ出力してください。その様な経路が存在しない場合は-1を出力してください。

ただし、長さが同じウォークが複数ある場合別物として考えます。

Constraints
制約

Input
入力

$N~M~s~t~K$
$u_0~v_0~c_0$
$u_1~v_1~c_1$
$u_2~v_2~c_2$
:
$u_{M-1}~v_{M-1}~c_{M-1}$

Output
出力

$x_1$
$x_2$
$\vdots$
$x_K$

# 1

4 5 0 3 5
0 1 1
1 2 1
2 3 1
0 2 1
1 3 1
2
2
3
-1
-1

Forum


Timelimit: 5 secs

Before submitting, please confirm terms and conditions