注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "diamonds.h"。

题目描述

题目译自 eJOI2025 Day1 T1. Collecting Diamonds

在罗多彼山脉发现了一个钻石矿床。为简单起见，我们假设该矿床有 $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 使用其策略将收集到的钻石总数。

输入格式

第一行包含三个整数：$N, M, K$ 的值。

第 $1+i$ 行包含三个整数 $u[i], v[i], d[i]$，代表一条从大厅 $u[i]$ 开始、到大厅 $v[i]$ 结束、可开采 $d[i]$ 颗钻石的走廊。

输出格式

第一行包含一个整数：该调用的返回值。

样例 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})

Petar 将选择通过以下走廊：$2 \xrightarrow{12} 3 \xrightarrow{8} 1 \xrightarrow{10} 4 \xrightarrow{9} 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})

有 $5$ 种通过 $4$ 条走廊的选项：

1. $0 \xrightarrow{7} 1 \xrightarrow{6} 0 \xrightarrow{7} 1 \xrightarrow{6} 0$；
2. $1 \xrightarrow{6} 0 \xrightarrow{7} 1 \xrightarrow{6} 0 \xrightarrow{7} 1$；
3. $2 \xrightarrow{7} 3 \xrightarrow{7} 4 \xrightarrow{1} 2 \xrightarrow{7} 3$；
4. $3 \xrightarrow{7} 4 \xrightarrow{1} 2 \xrightarrow{7} 3 \xrightarrow{7} 4$；
5. $4 \xrightarrow{1} 2 \xrightarrow{7} 3 \xrightarrow{7} 4 \xrightarrow{1} 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。

详细子任务附加限制及分值如下表所示。