Description

在罗多彼山脉发现了一处钻石矿床。为方便起见，设该矿床有 $N$ 个大厅，编号为 $0$ 到 $N-1$。有 $M$ 条单向走廊连接着若干大厅，并且 每个 大厅至少有一条走廊从它出发。每条走廊在通过时都能开采到一定数量的钻石。这个数量在多次通过时 不会变化——也就是说，重复通过该走廊，收集到的钻石数保持不变。

可能存在一条走廊把某个大厅连到自身；同一对大厅之间也可能存在多条走廊（包括方向相同的多条）。此外，也 不保证 所有大厅两两可达：即可能存在一对大厅 $(x, y)$，使得无法从 $x$ 到达 $y$。

Petar 将恰好通过 $K$ 条走廊来采集钻石。他会先选择某个大厅 $s$ 作为起点，然后沿一条从 $s$ 出发的走廊移动到下一个大厅，如此反复，直到恰好通过了 $K$ 条走廊为止。注意，他可以重复进入大厅与走廊；并且每次经过同一条走廊，收集到的钻石数量都不会改变。还要注意，总能找到一条可以连续通过 $K$ 条走廊的途径。

Petar 选择起点 $s$ 与行走路径的方式如下：首先，他希望 第一 条经过的走廊所获得的钻石数最大；在所有能使第一条走廊钻石数最大的方案中，他再选择 第二 条走廊钻石数最大的方案；以此类推，共进行 $K$ 次。换言之，Petar 想要选择 字典序最大 的走廊序列。他想知道在这种策略下，自己最终能收集到多少钻石。请帮助他计算这一总数。

实现细节

你需要实现函数 calculate_diamonds：

long long int calculate_diamonds(int N, int M, int K, std::vector<int> u, std::vector<int> v, std::vector<int> d)

• $N$：矿床中的大厅数；
• $M$：大厅之间的走廊数；
• $K$：Petar 将要经过的走廊数；
• $u$、$v$、$d$：长度为 $M$ 的整数向量，分别表示每条走廊的起点大厅、终点大厅以及该走廊可采的钻石数。

该函数在每个测试中被调用一次，并返回一个数——Petar 采用上述策略时能收集到的钻石总数。

Input Format

输入格式如下：

• 第 $1$ 行：三个整数——$N$、$M$、$K$。
• 第 $1 + i$ 行：三个整数 $u[i]$、$v[i]$、$d[i]$——表示一条从大厅 $u[i]$ 出发、到达大厅 $v[i]$ 的走廊，可采钻石为 $d[i]$。

Output Format

输出格式如下：

• 第 $1$ 行：一个整数——函数调用的返回值。

5 6 4
2 0 12
0 4 8
4 1 9
2 3 12
3 1 8
1 4 10

39

5 5 4
0 1 7
1 0 6
2 3 7
3 4 7
4 2 1

22

Hint

示例 1

考虑如下调用与示意图，$N = 5, M = 6, K = 4$：

calculate_diamonds(5, 6, 4, {2, 0, 4, 2, 3, 1}, {0, 4, 1, 3, 1, 4}, {12, 8, 9, 12, 8, 10})

:::align{center} :::

Petar 会选择经过如下走廊：$2 \overset{12}{\rightarrow} 3 \overset{8}{\rightarrow} 1 \overset{10}{\rightarrow} 4 \overset{9}{\rightarrow} 1$。他收集到的总钻石数为 $39$，这也是函数应返回的值。

示例 2

考虑如下调用与示意图，$N = 5, M = 5, K = 4$：

calculate_diamonds(5, 5, 4, {0, 1, 2, 3, 4}, {1, 0, 3, 4, 2}, {7, 6, 7, 7, 1})

:::align{center} :::

共有 $5$ 种经过 $4$ 条走廊的选择：

(1) $0 \overset{7}{\rightarrow} 1 \overset{6}{\rightarrow} 0 \overset{7}{\rightarrow} 1 \overset{6}{\rightarrow} 0$；

(2) $1 \overset{6}{\rightarrow} 0 \overset{7}{\rightarrow} 1 \overset{6}{\rightarrow} 0 \overset{7}{\rightarrow} 1$；

(3) $2 \overset{7}{\rightarrow} 3 \overset{7}{\rightarrow} 4 \overset{1}{\rightarrow} 2 \overset{7}{\rightarrow} 3$；

(4) $3 \overset{7}{\rightarrow} 4 \overset{1}{\rightarrow} 2 \overset{7}{\rightarrow} 3 \overset{7}{\rightarrow} 4$；

(5) $4 \overset{1}{\rightarrow} 2 \overset{7}{\rightarrow} 3 \overset{7}{\rightarrow} 4 \overset{1}{\rightarrow} 2$。

方案 (2) 与 (5) 不能使第一条走廊的钻石数最大；在方案 (1)、(3)、(4) 中，只有方案 (3) 能使 第二 条走廊的钻石数最大，因此它是 Petar 的最佳选择。注意，方案 (3) 并 不 使 第三 条走廊的钻石数最大，也 不 使总钻石数最大，但它是 唯一的字典序最大 序列。Petar 收集到的总钻石数为 $22$，这也是函数应返回的值。

约束

• $1 \leq N \leq 2000$
• $1 \leq M \leq 4000$
• $1 \leq K \leq 10^9$
• $0 \leq u[i], v[i] < N$
• 对每个 $0 \leq i < M$，$1 \leq d[i] \leq 10^9$
• 保证每个大厅至少有一条走廊从其出发。
• 注意：内存限制异常之小，仅为 4 MB。

子任务

翻译由 ChatGPT-5 完成。