← 返回题目列表

Codeforces · 1218/C

C. 跳跃变形金刚

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

你,强大的 Blackout,正站在 $$$N$$$x$$$M$$$ 矩阵的左上角 $$$(0,0)$$$ 角落。您必须每秒向右或向下移动。

有 $$$K$$$ 变压器按以下方式在矩阵中跳跃。每个变压器在 $$$t$$$ 时刻从位置 $$$(x,y)$$$ 开始跳转,并每秒跳转到下一个位置。 $$$x$$$ 轴向下增长,$$$y$$$ 轴向右增长。跳跃位置的顺序定义为$$${(x,y),(x+d,y-d),(x+d,y),(x,y+d)}$$$,并且是周期性的。在时间 $$$t$$$ 之前,变压器不在矩阵中。

你想要到达右下角$$$(N-1,M-1)$$$,同时杀死变形金刚并损失尽可能少的能量。当你在矩阵场中遇到变压器(或多个变压器)时,你必须将它们全部杀死,并且你会损失杀死每个变压器所需的能量总和。

变形金刚被杀后,他当然停止跳跃,坠入深渊并离开矩阵世界。输出尽可能少的能量浪费。

输入

第一行,整数 $$$N$$$,$$$M$$$ ($$$1 \leq N, M \leq 500$$$) 表示矩阵的大小, $$$K$$$ ($$$0 \leq K \leq 5*10^5$$$) 表示跳跃变压器的数量。

在接下来的 $$$K$$$ 行中,对于每个变压器,数字 $$$x$$$、$$$y$$$、$$$d$$$ ($$$d \geq 1$$$)、$$$t$$$ ($$$0 \leq t \leq N+M-2$$$) 和 $$$e$$$ ($$$0 \leq e \leq 10^9$$$),代表变压器的起始坐标,上述图案中跳跃位置的距离,变压器开始跳跃的时间,以及杀死它所需的能量。

保证变压器的所有4个跳跃点都在矩阵坐标内

输出

打印单个整数,即停电到达右下角时所浪费的最小可能量的能量。

示例

输入 #1

3 3 5
0 1 1 0 7
1 1 1 0 10
1 1 1 1 2
1 1 1 2 2
0 1 1 2 3

输出 #1

9

注意

如果 Blackout 采用从 (0, 0) 到 (2, 0) 的路径,然后从 (2, 0) 到 (2, 2),他将需要杀死第一个和第三个变压器,总能量成本为 9。不存在能量值更少的路径。