原题链接

Problem - 894E - Codeforces

1. 做完后记得选择这个选择题。 {{ select(1) }}

• 提交并且通过了
• 还没有提交，或者提交了 WA 了。

题目描述

Ralph 打算去蘑菇森林采蘑菇。

蘑菇森林里有 $n$ 个蘑菇丛，有 $m$ 条有向的路连接这些丛林（可能连向自己，也可能两个丛林之间有多条路）。

经过某条路时，Ralph 可以采走这条路上的全部蘑菇。然而，这是一片神奇的蘑菇森林，蘑菇被采走后会重新长出来一些。但是，第 $k$ 次走过这条路后，这条路上重新长出的蘑菇会比上次少 $k$。（举个例子，第一次有 $w$ 个蘑菇，第二次有 $w-1$ 个蘑菇，第三次有 $w-1-2$ 个蘑菇，以此类推……）（还有，蘑菇的数量大于 $0$）。

那么，Ralph 最多可以采到多少蘑菇呢？

输入格式

第一行输入两个整数 $n,m$。其中 $1\leq n,m\leq 10^6$

接下来 $m$ 行每行三个整数描述一条边的情况，三个整数用 $u,v,w$ 代表 $u\to v$ 有一条长度为 $w$ 的有向边。其中 $0\leq w\leq 10^8$。

最后一行包括一个整数 $s$，代表起始位置。

输出格式

打印一个整数，表示拉尔夫在行进路线上最多可以收集到的蘑菇数量。

2 2
1 2 4
2 1 4
1

16

3 3
1 2 4
2 3 3
1 3 8
1

8

提示

在第一个样本中，拉尔夫可以在圆圈上通过三次并收集到 4 + 4 + 3 + 3 + 1 + 1 = 16 个蘑菇。之后拉尔夫就再也收集不到蘑菇了。

在第二个示例中，破坏王可以前往 3 号树，并在 1 号树到 3 号树之间的路径上收集到 8 个蘑菇。