AdditionalFile5668.zip

#5668. 「JOI 2026 Final Day2」传送门 2

标签: 传统 | 时间限制: 3500 ms | 内存限制: 1024 MiB |

题目描述

题目译自 JOI 2026 Final Day2 T3 「テレポーター 2 / Teleporter 2」

在一条直路上有 $N$ 个地点，从左到右依次编号为 $1, 2, \ldots, N$。道路只能从左向右单向通行。

此外，还有 $M$ 个编号为 $1, 2, \ldots, M$ 的传送装置。使用装置 $i$ $(1 \leq i \leq M)$ 可以从地点 $S_i$ 瞬间移动到地点 $T_i$ $(S_i < T_i)$。

比太郎目前位于地点 $1$，并计划前往地点 $N$。当比太郎位于地点 $j$ $(1 \leq j \leq N-1)$ 时，他可以采取以下行动之一：

• 步行移动到地点 $j+1$。
• 选择一个满足 $S_i = j$ 的装置 $i$ $(1 \leq i \leq M)$，并利用该装置瞬间移动到地点 $T_i$。

众所周知，瞬间移动会对身体造成负担。为了保护比太郎的安全，你决定破坏 $0$ 个或多个传送装置，使得无论比太郎选择哪条路径，其瞬间移动的次数都处于 $K$ 次及以下。通过支付成本 $C_i$，可以破坏传送装置 $i$，装置一旦被破坏，比太郎便无法再使用它。

请计算在满足上述条件的前提下，破坏装置所需支付的最小总成本。

输入格式

第一行包含三个整数 $N, M$ 和 $K$。

接下来的 $M$ 行，其中第 $i$ 行包含三个整数 $S_i, T_i$ 和 $C_i$。

输出格式

输出一行，包含一个整数，表示可能的最少总成本。

样例 1

输入

8 4 1
1 4 3
2 3 5
3 6 2
5 8 2

输出

4

考虑破坏装置 $3$ 和 $4$ 的情况。

比太郎可使用的装置仅剩 $1$ 和 $2$。从地点 $1$ 移动到地点 $8$ 时，比太郎进行瞬间移动的次数必然在 $1$ 次及以下，满足条件。

此时支付的总成本为 $4$。由于成本无法降低至 $3$ 或更低，因此输出 $4$。

此样例满足所有子任务的限制。

样例 2

输入

12 7 2
1 5 3
4 8 2
2 4 5
2 4 8
7 9 4
9 11 7
3 10 5

输出

6

破坏装置 $2$ 和 $5$ 是最优的选择。

此样例满足子任务 $2, 3, 4, 5, 6$ 的限制。

样例 3

输入

6 3 2
1 4 2
2 5 4
3 6 3

输出

0

在这种情况下，不需要破坏任何装置。

此样例满足子任务 $2, 3, 4, 5, 6$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 100000$。
• $1 \leq K \leq M \leq 100000$。
• $1 \leq S_i < T_i \leq N$ $(1 \leq i \leq M)$。
• $1 \leq C_i \leq 10^9$ $(1 \leq i \leq M)$。
• 输入的所有数值均为整数。

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