← 返回题目列表

AtCoder · abc137_e

E. 硬币重生

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

分数: 500 点

问题陈述

有一个有向图 N 顶点编号 1 to N 和 M 边缘。 的 i第一条边从顶点定向 A_i 到顶点 B_i,并且有 C_i 沿着该边缘放置硬币。 此外,Vertex 上还有一个按钮 N.

我们将在此图上玩一个游戏。 您在 Vertex 上开始游戏 1 零金币,前往顶点 N 通过在收集硬币时遍历边缘。 穿过一条边需要一分钟,每次穿过边都可以收集沿边放置的硬币。 和游戏中一样,即使您遍历一次边缘并收集硬币,下次遍历该边缘时也会再次出现相同数量的硬币,您可以再次收集这些硬币。

当你到达顶点时 N,按下按钮即可结束游戏。 (您也可以选择离开Vertex N 无需按下按钮并继续行驶。) 但是,当你结束游戏时,你会被要求付费 T \times P 硬币,在哪里 T 是自比赛开始以来经过的分钟数。如果你有少于 T \times P 硬币,您将必须支付所有硬币。

您的分数将是您在此次付款后拥有的硬币数量。 判断是否存在可以获得的分数的最大值。如果答案是肯定的,请找到该最大值。

约束

  • 2 \leq N \leq 2500
  • 1 \leq M \leq 5000
  • 1 \leq A_i, B_i \leq N
  • 1 \leq C_i \leq 10^5
  • 0 \leq P \leq 10^5
  • 输入中的所有值都是整数。
  • 顶点 可以从 Vertex 到达 N 可以从顶点到达 1.

输入

输入由标准输入按以下格式给出:

N M P
A_1 B_1 C_1
:
A_M B_M C_M

输出

如果存在可以获得的分数的最大值,则打印该最大值;否则,打印 -1.


示例输入 1

3 3 10
1 2 20
2 3 30
1 3 45

示例输出 1

35

Figure of the graph given in Sample Input 1

从顶点出发有两种方式 1 到顶点 3:

  • 顶点 可以从 Vertex 到达 1 \rightarrow 2 \rightarrow 3:你收集 20 + 30 = 50 硬币正在路上。游戏开始两分钟后,您按下按钮,支付 2 \times 10 = 20 硬币,你有 还剩 50 - 20 = 30 硬币。
  • 顶点 可以从 Vertex 到达 1 \rightarrow 2:你收集 45 硬币正在路上。游戏开始一分钟后,您按下按钮,支付 1 \times 10 = 10 硬币,你有 还剩 45 - 10 = 35 硬币。

因此,可以获得的最高分数是 35.


示例输入 2

2 2 10
1 2 100
2 2 100

示例输出 2

-1

Figure of the graph given in Sample Input 2

从顶点延伸的边 1 带你去顶点 2。如果然后遍历从顶点延伸的边 2 对自己 t 次并按下按钮,您的分数将为 90 + 90t。因此,你可以无限地增加你的分数,这意味着可以获得的分数没有最大值。


示例输入 3

4 5 10
1 2 1
1 4 1
3 4 1
2 2 100
3 3 100

示例输出 3

0

Figure of the graph given in Sample Input 3

没有办法从 Vertex 出发 1 到顶点 4 除了遍历从顶点开始的边之外 直接 1 到顶点 4 。你会沿着这个边缘捡起一枚硬币,但在被要求付款后 10 硬币,你的分数将为 0.

请注意,如果你穿过从顶点开始的边,你可以收集无限数量的硬币 1 到顶点 2,但这毫无意义,因为你无法再到达 Vertex 4 并结束游戏。