洛谷 P4009 汽车加油行驶问题
题目描述
给定一个 的方形网格,设其左上角为起点◎,坐标 , 轴向右为正, 轴向下为正,每个方格边长为 ,如图所示。
一辆汽车从起点◎出发驶向右下角终点▲,其坐标为 。
在若干个网格交叉点处,设置了油库,可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则。汽车只能沿网格边行驶,装满油后能行驶 条网格边。出发时汽车已装满油,在起点与终点处不设油库。
汽车经过一条网格边时,若其 坐标或 坐标减小,则应付费用 ,否则免付费用。
汽车在行驶过程中遇油库则应加满油并付加油费用 。
在需要时可在网格点处增设油库,并付增设油库费用 (不含加油费用 )。
均为正整数, 且满足约束: ,。
设计一个算法,求出汽车从起点出发到达终点所付的最小费用。
输入格式
文件的第一行是 的值。
第二行起是一个 的 方阵,每行 个值,至 行结束。
方阵的第 行第 列处的值为 表示在网格交叉点 处设置了一个油库,为 时表示未设油库。各行相邻两个数以空格分隔。
输出格式
程序运行结束时,输出最小费用。
输入输出样例
输入 #1
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
输出 #1
12
说明/提示
,。
分析
在坐标 可以有多种选择:加油、设立油库、增加坐标、减小坐标。每种选择会产生不同的花费,可以考虑分层图最短路。
建立 层图,每一层图上有 个节点;层数从 开始编号,第 层表示该层的所有节点代表的状态油量为 ,。在网格图中位于坐标 且油量为 的状态对应节点 。
车在网格图上行走,每走一步油量会减少 ,因此第 层的节点要向 层连边,若增大坐标,不产生费用,边权为 ,否则边权为 ;遇到油库,必须将油加满,会产生费用 ,因此有油库的点无条件向 层的对应节点连边,边权为 ;若节点没用油库,但是新设立油库,这时候贪心的考虑,不能走回头路再来加油,应当设立新油库后马上加油,费用为 ,因此无油库的点向 层的对应节点连边,边权为 。初始状态代表的节点为 ,建完图后使用 算法即可求出图上的单源最短路,答案取 即可, 指 两节点间的最短距离。
代码
1 | /****************************************************************** |