← 返回题目列表

AtCoder · joi2026final_f

F. 传送器2(传送器2)

中文机器翻译题面 查看原题

分数: 100 点

问题陈述

有 N 直线路径上的点,编号 1, 2, \ldots, N 从左到右。 该路径是从左到右的单向路径。

还有 M 传送器设备编号 1, 2, \ldots, M。 通过使用设备 i (1 \leq i \leq M),可以从点扭曲 S_i 来点 T_i (S_i < T_i).

Bitaro 目前处于该位置 1 并想要达到目标 N。 当比特罗在位时 j (1 \leq j \leq N-1),他可以采取以下操作之一:

  • 步行至点 j+1.
  • 选择一个 i (1 \leq i \leq M) 满意 S_i = j,使用设备 i,并扭曲到点 T_i.

众所周知,曲速旅行会给身体带来压力。 你担心Bitaro的安全,所以决定摧毁零个或多个传送装置,这样,无论Bitaro走哪条路线,曲速旅行的次数最多为 K。 设备 i 可以通过支付费用来破坏 C_i;如果是这样,Bitaro 将无法再使用该设备。

找出摧毁零个或多个传送器设备时需要支付的最小可能总成本,以便无论 Bitaro 的路线如何,曲速旅行的次数最多为 K.


输入

从标准输入读取以下数据。

N M K
S_1 T_1 C_1
S_2 T_2 C_2
\vdots
S_M T_M C_M

输出

将一行写入标准输出,其中包含可能的最小总成本。


约束

  • 2 \leq N \leq 100\,000.
  • 1 \leq K \leq M \leq 100\,000.
  • 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).
  • 给定值均为整数。

子任务

  1. (5 点) K=1.
  2. (3 点) N \leq 20, M \leq 20.
  3. (29 点) N \leq 500, M \leq 500.
  4. (23 点) N \leq 4\,000, M \leq 4\,000.
  5. (24 点) N \leq 40\,000, M \leq 40\,000.
  6. (16 点)没有额外的限制。

示例输入 1

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

示例输出 1

4

考虑设备 3 和 4 被摧毁。

那么 Bitaro 只能使用设备 1 和 2。 从点移动时 1 来点 8,Bitaro 总是最多进行一次曲速旅行,因此满足条件。

在这种情况下,支付的总成本为 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

示例输出 2

6

销毁设备 2 和 5 是最佳的。

该输入示例满足子任务的约束 2,3,4,5,6.


示例输入 3

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

示例输出 3

0

在这种情况下,无需销毁任何设备。

该输入示例满足子任务的约束 2,3,4,5,6.