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