B - Hawker on Graph /

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