2928. 汽车加油行驶问题

单点时限: 2.0 sec

内存限制: 256 MB

给定一个 N*N 的方形网格,设其左上角为起点◎,坐标为(1,1),X 轴向右为正,Y

轴向下为正,每个方格边长为 1。一辆汽车从起点◎出发驶向右下角终点▲,其

坐标为(N,N)。在若干个网格交叉点处,设置了油库,可供汽车在行驶途中加油。汽车在

行驶过程中应遵守如下规则:

(1) 汽车只能沿网格边行驶,装满油后能行驶 K 条网格边。出发时汽车已装满油,在起

点与终点处不设油库。

(2) 汽车经过一条网格边时,若其 X 坐标或 Y 坐标减小,则应付费用 B,否则免付费用。

(3) 汽车在行驶过程中遇油库则应加满油并付加油费用 A。

(4) 在需要时可在网格点处增设油库,并付增设油库费用 C (不含加油费用 A)。

(5)(1)~(4) 中的各数 N、K、A、B、C 均为正整数,且满足约束:2 <= N <= 100,2 <= K <= 10。

设计一个算法,求出汽车从起点出发到达终点的一条所付费用最少的行驶路线。

输入格式

第一行是 N,K,A,B,C 的值。第二行起是一

个 N*N 的 0-1 方阵,每行 N 个值,至 N+1 行结束。方阵的第 i 行第 j 列处的值为 1 表示在

网格交叉点(i,j)处设置了一个油库,为 0 时表示未设油库。各行相邻两个数以空格分隔。

输出格式

输出最小费用

样例

Input
9 3 2 3 6
0 0 0 0 1 0 0 0 0
0 0 0 1 0 1 1 0 0
1 0 1 0 0 0 0 1 0
0 0 0 0 0 1 0 0 1
1 0 0 1 0 0 1 0 0
0 1 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0 1
1 0 0 1 0 0 0 1 0
0 1 0 0 0 0 0 0 0
Output
12

7 人解决,9 人已尝试。

14 份提交通过,共有 36 份提交。

6.4 EMB 奖励。

创建: 13 年,11 月前.

修改: 2 年,5 月前.

最后提交: 3 年前.

来源: zzz-周正中

题目标签