文件名称:
汽车最少费用加油行驶 ACM题目的作业
开发工具:
文件大小: 48kb
下载次数: 0
上传时间: 2009-04-13
详细说明： 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 ...展开收缩
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
