← 返回题目列表

AtCoder · joi2008ho_d

D. 跳过河

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

配点: 20 点

在一条河里,同时从一岸跳到石头上,再跳到对岸,这种有些危险的游戏很流行。

图 4-1 石头的位置示例

现在,像图 4-1 那样,假设石头存在于格子上。行数是 n 。在图 4-1 中是 n = 5 。

在这个游戏中,从一岸开始,通常跳跃或者 m 次以下的一行跳跃,渡到对岸。通常跳跃是指跳到当前行的下一行的岸或石头上,而一行跳跃是指跳到当前行的下一下一行的岸或石头上。开始岸的下一行是 1 行,下一下一行是 2 行,而n − 1 行的下一下一行,以及 n 假设一行的下一行是对岸。

现在,为了尽可能安全地完成这个游戏,我们决定考虑跳跃的危险度。每块石头都有其滑溜程度。从一块石头跳到另一块石头时的跳跃危险度,无论是普通跳跃还是跨一行跳跃,

  • (当前石头的滑溜程度 + 跳到的石头的滑溜程度)\times(横向移动距离) 来决定。不过,横向移动距离是指列号的差值。此外,从岸边跳到石头,或者从石头跳到岸边的跳跃危险度为 0 。

输入为 n, m,当给定每块石头的位置和滑溜程度时,编写一个程序求出到达对岸时跳跃危险度的最小值中的最小值。所给的输入数据保证一定能够到达对岸,并且同一个格子中石头不超过 2 块。


入力

输入文件的文件名是 input.txt 。

输入文件的 1 行中,用空格分隔地写着 2 整数 给出 n,m 。这表示行数,以及允许跳过一行的次数。n,m 分别是 代表第 2\leqq n\leqq 150,0\leqq m\leqq \dfrac{(n+1)}2 得到满足。

继续 n 行中,分别写着每行中石头的信息。i+1 行目 (1 \leqq i \leqq n)中有1 整数 k_i (0 \leqq k_i \leqq 10),随后写有 2 \times k_i 个整数,用空格分开。这些表示从起始岸数起,第 i 行中石头的信息。

k_i 表示该行存在的石头数量,接下来的 2 \times k_i 个整数中, 2 \times j - 1 個目 (1 \leqq j \leqq k_i) 的整数 x_{i,j} 表示该行的第 j 块石头的列号,2 \times j 个整数中的第 d_{i,j} 表示该行的第 j 块石头的滑溜度分别表示。x_{i,j},d_{i,j} 分别是 代表第 1 \leqq x_{i,j} , d_{i,j} \leqq 1000 得到满足。

评分数据中,分配的分数 20 对于%, n \leqq 6 和另一个点分配 20 对于%, m = 0 得到满足。

出力

输出文件的文件名是 output.txt 。

output.txt 表示到达对岸时总跳跃风险的最小值 包含 1 整数 由 1 行组成。

例

在图4-2中,石子上写的数字代表每块石子的滑性。

按照箭头指示的顺序穿过石头时,每次跳跃的风险为 0,(2 + 2) \times 1 = 4,(2 + 1) \times 1 = 3,(1 + 4) \times 2 = 10,0 总计为 17 变为。此时,跳跃的总风险是最小的。

该示例对应于输入/输出示例。

图 4-2 路由示例


入力例 1

5 1
2 1 3 2 2
1 3 2
1 1 7
1 2 1
1 4 4

出力例 1

17

上例对应的输入输出如例1。


入力例 2

5 0
2 1 3 2 2
1 3 2
1 1 7
1 2 1
1 4 4

出力例 2

40