← 返回题目
题库练习 [ABC137E] Coins Respawn
← 上一题 下一题 →

A7609 | [ABC137E] Coins Respawn

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

有一个由 $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
4 5 10
1 2 1
1 4 1
3 4 1
2 2 100
3 3 100
输出 #3
0
C++ 编辑器
输入
输出