AT_abc137_e.[ABC137E] Coins Respawn

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个由 $N$ 个编号为 $1$ 到 $N$ 的顶点和 $M$ 条边组成的有向图。第 $i$ 条边从顶点 $A_i$ 指向顶点 $B_i$ ，这条边上放有 $C_i$ 枚硬币。此外，顶点 $N$ 上安装有一个按钮。

你将在这张图上进行游戏。你从顶点 $1$ 出发，初始时持有 $0$ 枚硬币，沿着边移动并拾取硬币，目标是到达顶点 $N$ 。每经过一条边需要 $1$ 分钟，并且每次经过一条边时都可以拾取该边上所有的硬币。和游戏世界常见设定一样，即使你已经经过某条边并拾取了硬币，下次再经过时该边上的硬币会再次出现，你仍然可以再次拾取。

到达顶点 $N$ 时，你可以按下按钮结束游戏（也可以选择不按按钮继续移动）。不过，结束游戏时，假设从游戏开始已经过去了 $T$ 分钟，你需要支付 $T \times P$ 枚硬币。如果你持有的硬币不足 $T \times P$ ，则需要支付你持有的全部硬币。

支付后剩下的硬币数就是你的得分。请判断是否存在可以获得的最大得分，如果存在则输出最大得分，否则输出 $-1$ 。

输入格式

输入以如下格式从标准输入读入。

$N$ $M$ $P$
$A_1$ $B_1$ $C_1$
$\vdots$
$A_M$ $B_M$ $C_M$

输出格式

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

输入输出样例

输入#1
```
3 3 10
1 2 20
2 3 30
1 3 45
```
输出#1
```
35
```
输入#2
```
2 2 10
1 2 100
2 2 100
```
输出#2
```
-1
```

输入#3

输出#3

说明/提示

限制条件

$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$
输入中的所有值均为整数。
一定可以从顶点 $1$ 到达顶点 $N$ 。

样例解释 1

输入例 1 所给图的示意图

从顶点 $1$ 到顶点 $3$ 有以下两种方式：

$1 \rightarrow 2 \rightarrow 3$ ：途中共拾取 $20 + 30 = 50$ 枚硬币。到达顶点 $3$ 时已过去 $2$ 分钟，支付 $2 \times 10 = 20$ 枚硬币，剩下 $50 - 20 = 30$ 枚。
$1 \rightarrow 3$ ：途中拾取 $45$ 枚硬币。到达顶点 $3$ 时已过去 $1$ 分钟，支付 $1 \times 10 = 10$ 枚硬币，剩下 $45 - 10 = 35$ 枚。

因此，最大得分为 $35$ 。

样例解释 2

输入例 2 所给图的示意图

从顶点 $1$ 出发经过一条边到达顶点 $2$ ，然后可以在顶点 $2$ 上自环多次，每次都能拾取 $90$ 枚硬币。这样，最终得分为 $90 + 90t$ ，可以无限增加。因此不存在最大得分。

样例解释 3

输入例 3 所给图的示意图

从顶点 $1$ 到顶点 $4$ 只有一条直接的边。经过这条边可以拾取 $1$ 枚硬币，但结束时需要支付 $10$ 枚硬币，因此得分为 $0$ 。

注意，虽然可以从顶点 $1$ 到顶点 $2$ 并在 $2$ 上无限拾取硬币，但无法到达顶点 $4$ 并结束游戏，因此没有意义。

首页