Time Limit: 6 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N 頂点 M 辺の重み付き有向グラフ G があります。 G の頂点には 1, 2, \ldots, N、辺には 1, 2, \ldots, M と番号が振られています。 辺 i は頂点 u_i から頂点 v_i へ張られており、辺の重みは w_i です。 あなたは、G 上で次のようなゲームをします。
初めに、所持金 W 円を持って頂点 S 上に立つ。その後、以下の操作を K 回行う:
- 自分の今いる頂点から出ている辺を 1 つ選んで、その辺が接続する頂点に移動する。
- このとき、選んだ辺の重みを w とすると、w が正ならば w 円得る。逆に w が負ならば |w| 円失う。また、所持金が負となることはない。すなわち、元の所持金を t 円とすると、移動後の所持金は \mathrm{max}(t+w, 0) 円である。
同じ辺を何度通ってもよく、通るたびに所持金が変化します。 K 回の操作を完了する前に、移動が不可能になる頂点に訪れては行けません。 また、ゲーム終了時はどの頂点に立っていても構いません。
このとき、ゲーム終了時の所持金は最大でいくらにできるかを求め、出力してください。 ただし、どのように操作を行っても K 回の操作を完了できない場合は、-1 を出力してください。
制約
- 2 \leq N \leq 200
- 0 \leq M \leq N (N-1)
- 0 \leq W \leq 10^{16}
- 1 \leq S \leq N
- 1 \leq K \leq 10^9
- 1 \leq u_i, v_i \leq N (1 \leq i \leq M)
- -10^7 \leq w_i \leq 10^7 (1 \leq i \leq M)
- u_i \neq v_i (1 \leq i \leq M)
- i \neq j ならば (u_i, v_i) \neq (u_j, v_j)
入力
入力は以下の形式で標準入力から与えられる。
N M W S K u_1 v_1 w_1 : u_M v_M w_M
出力
K 回の操作を完了できる場合には、ゲーム終了時の所持金の最大値を出力せよ。 どのように操作を行っても完了できない場合は、-1 を出力せよ。
入力例 1
5 6 0 1 5 1 2 1 2 3 2 3 4 1 4 1 -1 3 1 -4 2 5 7
出力例 1
8
頂点を 1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 5 と移動すれば、所持金は 8 円となります。
入力例 2
5 6 10 1 4 1 2 1 1 3 3 2 4 6 5 4 0 3 5 2 2 5 1
出力例 2
-1
どのように操作を行っても 4 回の操作を完了することはできません。したがって -1 を出力します。
入力例 3
2 2 0 2 1000000000 1 2 100000 2 1 100000
出力例 3
100000000000000