文件名称：汽车最少费用加油行驶 ACM题目的作业
文件大小：48KB
文件格式：DOC
更新时间：2012-05-03 10:01:27
汽车最少费用 最少费用问题 ACM 程序 代码
Problem D:汽车最少费用加油行驶 Description 给定一个 N*N 的方形网格, 设其左上角坐标为 (1, 1), X 轴向右为正, Y 轴向下为正, 每个方格边长为 1, 右下角坐标为 (N, N). 一辆已装满油的汽车从 (1, 1) 为起点出发驶向终点 (N, N). 在若干个网格交叉点处设有油库供汽车在行驶途中加油, 在起点与终点处不设油库. 汽车在行驶过程中遵守如下规则: 1. 只能沿网格边行驶, 装满油后能行驶 K 条网格边 2. 当行驶经过一条网格边时, 若其 X 坐标或 Y 坐标减小, 则应付费用 B, 否则免付费用 3. 在行驶过程中遇油库则应加满油并付加油费用 A 4. 在需要时可在网格点处增设油库, 并付增设油库费用 C (不含加油费用A) 上述各数中的 N, K, A, B, C 均为正整数. 求汽车从起点出发到达终点的一条所付费用最少的行驶路线所需要的费用. Input 输入数据的第一行是 N, K, A, B, C 的值, 2 ≤ N ≤ 100, 2 ≤ K ≤ 10. 第二行起是一个 N*N 的 0-1 方阵, 每行 N 个值, 至 N+1 行结束. 方阵的第 i 行第 j 列处的值为 1 表示在网格交叉点 (i, j) 处设置有一个油库, 为 0 时表示未设有油库. 各行相邻的两个数以空格分隔. Output 对于测试用例的输入数据, 在一行上输出最优行驶路线所需的费用, 即最小费用. Sample 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 Sample Output 12