Coins Respawn

题目描述

有一个有向图，顶点编号为 $1$ 到 $N$，共有 $M$ 条边。 第 $i$ 条边是从顶点 $A_i$ 指向顶点 $B_i$，该边上放有 $C_i$ 枚硬币。 此外，在顶点 $N$ 上有一个按钮。 我们将在此图上进行一个游戏。 你从顶点 $1$ 开始游戏，初始拥有零枚硬币，沿着边前往顶点 $N$，并在行进途中收集硬币。 每次 traversing 一条边需要一分钟，并且每次经过该边都可以收集放在该边上的硬币。 像游戏中常见的规则一样，即使你只经过一条边一次并收集了硬币，下次再次经过该边时相同数量的硬币会重新出现，你可以再次收集。 当你到达顶点 $N$ 时，可以按下按钮结束游戏。（你也可以选择离开顶点 $N$ 不按按钮并继续旅行。） 然而，当你结束游戏时，需要支付 $T \times P$ 枚硬币，其中 $T$ 是从游戏开始到结束经过的分钟数。如果你拥有的硬币少于 $T \times P$，则需要把你所有的硬币都支付出去。 你的得分为支付之后你剩下的硬币数量。 判断是否存在一个可以获得的得分的最大值。如果存在，找出该最大值。

输入格式

输入从标准输入按以下格式给出： $N$ $M$ $P$ $A_1$ $B_1$ $C_1$ : $A_M$ $B_M$ $C_M$

输出格式

如果存在可以获得的得分的最大值，输出该最大值；否则，输出 $-1$。

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

35

2 2 10
1 2 100
2 2 100

-1

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

0

提示

$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$ 输入中的所有值均为整数。 顶点 $N$ 可以从顶点 $1$ 到达。 从顶点 $1$ 到顶点 $3$ 有两种行进方式：

顶点 $1 \rightarrow 2 \rightarrow 3$：你在路上收集到 $20 + 30 = 50$ 枚硬币。游戏开始后经过两分钟，你按下按钮，支付 $2 \times 10 = 20$ 枚硬币，剩下 $50 - 20 = 30$ 枚硬币。 顶点 $1 \rightarrow 2$：你在路上收集到 $45$ 枚硬币。游戏开始后经过一分钟，你按下按钮，支付 $1 \times 10 = 10$ 枚硬币，剩下 $45 - 10 = 35$ 枚硬币。

因此，可以获得的最大得分是 $35$。
从顶点 $1$ 出发的边会到达顶点 $2$。如果你随后对从顶点 $2$ 到它自身的那条边重复遍历 $t$ 次然后按下按钮，你的得分将是 $90 + 90t$。因此，你可以让得分无限增加，这意味着不存在得分的最大值。
除直接从顶点 $1$ 到顶点 $4$ 的那条边之外，没有其他从顶点 $1$ 到顶点 $4$ 的路径。你会在这条边上捡到一枚硬币，但在被要求支付 $10$ 枚硬币之后，你的得分将是 $0$。 注意如果你重复遍历从顶点 $1$ 到顶点 $2$ 的那条边可以无限收集硬币，但这是无意义的，因为你之后无法再到达顶点 $4$ 结束游戏。

标签: AtCoder|abc137E

来源

AtCoder|abc137E