← 返回题目列表

AtCoder · ddcc2020_final_b

B. 图上的小贩

中文机器翻译题面 查看原题

配点 : 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