J13 实践-4 大富翁游戏

题目描述

玩家小喵发明了一款新 · 大富翁游戏，邀请了他的朋友们一起来玩。 新 · 大富翁的地图有 $N$ 个据点 $M$ 条道路，其中第 $i$ 条道路能从据点 $A_i$ 走到据点 $B_i$ ，且这条路上有 $C_i$ 枚金币。 玩家从据点 $1$ 出发，出发时没有金币。每次花费 $1$ 分钟来走一条道路，并收集这条路上的金币。在这条路被走过后，金币将会被重置，再次通过这条路能再次收集到这些金币。 如果玩家想结束游戏，他需要走到终点——据点 $N$ ，并摁下位于据点 $N$ 的结束按钮（也可以不摁结束按钮继续玩）。结束后玩家还要再支付 $T\times P$ 枚金币的路费（$T$ 为玩游戏的分钟数），若手中的金币数不足 $T\times P$ ，就要付完所有的金币。当付完后，剩下的金币就是玩家的收获。 小喵想知道，他发明的这款新 · 大富翁游戏，玩家最多能得到多少枚金币。

输入格式

共 $M+1$ 行： 第一行三个整数 $N,M,P$ ，表示据点数量，道路数量和路费参数 $2$ ； 接下来的 $M$ 行每行三个整数 $A_i,B_i,C_i$ ，依次表示第 $i$ 条道路的起点，终点和金币数量。

输出格式

一行一个整数，输出玩家最多能获得的金币数；若没有最大值，输出 -1 。

输入样例

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

输出样例

35

样例分析

新 · 大富翁游戏的地图如上图所示，有 $2$ 种方法从据点 $1$ 走到据点 $3$ ：

• $1 \rightarrow 2 \rightarrow 3$ ：收集 $20+30=50$ 枚金币，花费 $2$ 分钟，需要支付 $2\times 10=20$ 枚金币作为路费，最终获得 $30$ 枚金币；
• $1 \rightarrow 3$ ：收集 $45$ 枚金币，花费 $1$ 分钟，需要支付 $1\times 10=10$ 枚金币作为路费，最终获得 $35$ 枚金币；

所以能获得最多的金币数为 $35$ 。

数据范围

对于 $100\%$ 的数据：$2≤N≤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$ ，保证所有输入都是整数。