2799. 区间覆盖

单点时限: 5.0 sec

内存限制: 256 MB

给定 $n$ 个点,$m$ 个操作,每次操作可以将第 $L_i$ 个点到第 $R_i$ 个点覆盖,耗费是 $W_i$。

问至少覆盖(可以重复覆盖) $k$ 个点的最小耗费是多少?

输入格式

第 1 行:一个整数 $T (1\leq T\leq 10)$ 为问题数。

接下来 $T$ 组测试数据,每组测试数据按如下格式输入:

第一行包含 3 个整数 $n,m,k(1\le n \le 300, 1\le m\le 10^5,1\le k\le n)$。

接下来 $m$ 行,每行包含 3 个整数 $L_i,R_i,W_i(1\le L_i \le R_i \le n,1 \le W_i \le 10^9)$

输出格式

对于每个问题,输出一行问题的编号(0 开始编号,格式:case #0: 等)。

然后对应每个问题 , 在一行中输出最小耗费,如果不能覆盖 k 个点输出 -1。

样例

Input
3
10 4 6
7 9 11
6 9 13
7 7 7
3 5 6
10 7 1
3 4 15
8 9 8
5 6 8
9 10 6
1 4 2
1 4 10
8 10 13
10 5 5
7 9 18
3 6 12
1 2 4
5 7 5
6 10 30
Output
case #0:
17
case #1:
2
case #2:
9

179 人解决,201 人已尝试。

235 份提交通过,共有 628 份提交。

2.4 EMB 奖励。

创建: 8 年,4 月前.

修改: 6 年,11 月前.

最后提交: 3 月,3 周前.

来源: N/A

题目标签
DP