2799. 区间覆盖

单点时限: 5.0 sec

内存限制: 256 MB

给定 个点, 个操作,每次操作可以将第 个点到第 个点覆盖,耗费是

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

输入格式

第 1 行:一个整数 为问题数。

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

第一行包含 3 个整数

接下来 行,每行包含 3 个整数

输出格式

对于每个问题,输出一行问题的编号(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

11 人解决,12 人已尝试。

25 份提交通过,共有 58 份提交。

4.9 EMB 奖励。

创建: 3 年前.

修改: 1 年,7 月前.

最后提交: 10 月,2 周前.

来源: N/A

题目标签
DP