首页 > ACM题库 > HDU-杭电 > hdu 2453 Carrying Out A Task-Dijkstra-[解题报告]C++
2014
01-26

hdu 2453 Carrying Out A Task-Dijkstra-[解题报告]C++

Carrying Out A Task

问题描述 :

During the process of the military exercise, there is a ship on the sea level .The ship will go to certain place to carry out a task. For every action, the ship has two ways to sail. They are normal sailing and accelerated sailing. The normal speed of the ship is certain, when the ship sails normally, it can only move 1 step to the adjacent normal sea level. The ship can also accelerate. There are 2 kinds of accelerated sailings, one is moving forward d steps (d <= 5) in a straight line, and it must move forward d steps exactly every time it accelerates, The d steps must be on the normal sea level, otherwise, it can not accelerate. The other is accelerating while getting through the undercurrent. There are a lot of undercurrents on the sea, and entering the undercurrent area needs to accelerate when the ship is 1 step to the undercurrent. However, the ship itself will be damaged more or less by the undercurrent, After entering the undercurrent, the speed of the ship will become normal immediately. Every time it accelerates, the ship has to consume a certain B energy, and when it starts up ,it carries certain B energy.

While the ship is sailing on the sea, it needs to consume a certain A energy. One unit of distance will consume one unit of A energy, and when the ship starts up, it carries enough A energy.

There are many reefs on the sea, and the ship can not get through.

Now the ship is required to sail to the certain place, of course, to minimize the damage to the ship itself is a priority because the cost of ships is very expensive. The damage is, of course, the smaller, the better. At the same time, an attempt should be made to control the consumption of A energy to the smallest amount during the whole process because the cost of A energy is much more expensive than that of B energy, and you can use B energy which the ship carried when it started up as you wish.

Now the question is to work out the minimal times of action from the departure point to the destination under the condition that to minimize the damage to the ship is a priority and then the consumption of A energy to the smallest degree.

输入:

The input file contains several test cases, the first line contains an integer T, indicates the number of test cases. In each case the first line includes two integers n, m (5 <= n, m <= 20), which indicate the size of the sea level for military exercises, and n rows and m columns are the current state of the sea level (‘S’ indicates the ship’s initial position, ‘E’ indicates the destination place, ‘#’ indicates the reefs, ‘*’ indicates the undercurrent , ‘ ‘ the normal sea level), followed a line with a number d in it, it indicates the distance of the first kind of acceleration, then another line includes two integers, indicate that the initial value of the B energy and the value of the B energy needed while accelerating every time.

输出:

The input file contains several test cases, the first line contains an integer T, indicates the number of test cases. In each case the first line includes two integers n, m (5 <= n, m <= 20), which indicate the size of the sea level for military exercises, and n rows and m columns are the current state of the sea level (‘S’ indicates the ship’s initial position, ‘E’ indicates the destination place, ‘#’ indicates the reefs, ‘*’ indicates the undercurrent , ‘ ‘ the normal sea level), followed a line with a number d in it, it indicates the distance of the first kind of acceleration, then another line includes two integers, indicate that the initial value of the B energy and the value of the B energy needed while accelerating every time.

样例输入:

2
5 10
##########
#E       #
#*###### #
#S       #
##########
5
10 2
6 10
##########
#E       #
#*######*#
#*######*#
#S       #
##########
5
3 2

样例输出:

8
can not reach!

简述一下题意:

20*20的地图上,一个起点S,一个终点E,障碍物#,漩涡*

一艘船从起点出发,携带充足的A类油和X升B类油。

沿上下左右四个方向行驶,不能在障碍物的格子行驶;可以进入漩涡,但每次进入船会受伤。没走过一个格子都要消耗一升A类油。

每个回合有两个操作:

1.普通航行一格

2.加速一次消耗Y升B类油,有两种加速方法,加速规则:

    a.在某一个方向连续航行d步,d步之内不能有障碍物、漩涡,不能驶出地图

    b.当下一步要驶入漩涡时,必须加速、进入漩涡后加速效果消失

询问船是否可以到达终点,输出最少多少个回合到达,前提——船受到的伤害最小(进入漩涡次数最少),其次消耗A类油最少(走过的格子数最少),再次回合数最少。

—–

首先这道题不要想的太复杂了,实质是常见的优先队列广搜(一致代价搜索)。

船最多可以加速的次数:[X/Y],而且很容易想到每个格子最多加速一次,所以用20*20*400判重(x坐标*y坐标*加速次数)

先预处理每个格子4个方向是否可以前进连续d步(a类加速);

广搜结构体中记录:

x——横坐标

y——纵坐标

oil——加速次数

unt——进入漩涡次数

t——路过的格子数

step——回合数

优先级:unt小/unt相等,t小/unt相等,t相等,step小

判重:[x][y][oil]

每次广搜时,扩展出的节点条件:oil<=X/Y

用priority_queue做广搜,20*20*400=1.6*10^5个节点、1.28*10^6条边的优先队列广搜

这样子写TLE了,不过离AC已经很近了。

—–

贪心优化:用二维数组记录每个位置进入漩涡次数,如果大于记录值就不用搜了;即加入扩展节点条件:les[x][y]<0 || unt<=les[x][y]

比如:

初始化les[20][20]为-1

栈顶struct在(2,3)这个点的unt为2,那么les[2][3]=2;

如果搜索过程再次弹出了一个栈顶struct在(2,3)这个点的unt为5,那么不扩展、直接continue;

其实这个优化就是平时我们常见的dijkstra中的d[]数组,所以这道题目我还是搞复杂了,实际上只是一个dijkstra+heap的题目而已。

—–

dijkstra的d[]数组

n个节点,m条边的无向图;dijkstra几种常见写法:

1.n^2的写法,这个不用多说。

2.O(m*log(m)),优先队列广搜/一致代价搜索,由于priority_queue不能进行定位,只用标记数组判重。

3.O(m*log(n)),手写堆、用一个辅助数组进行定位,保证堆里只有n个数;用set虽然也可以实现,但set和二叉堆比起来常数太大。

4.最坏O(m*log(m)),实际上接近O(m*log(n)),常见的dijkstra+heap都是这种复杂度,由于d[]数组的存在使堆里的元素大幅度减少;如果第二种写法加入d[]数组也是同样的。

5.利用fib堆,实现O(nlogn+m),由于fib堆很难写、很罕见。

对于这道题而言,O(m*log(m))会超时,但O(m*log(n))则可以AC(大约800MS),慢就慢在常数级别上了。由于只有400个点,建议先用floodfill判断起点、终点是否连通(把漩涡看做普通格子),如果不连通则一定无解,可以大大提高效率。

在平时做题中,我真的没有遇到过卡O(m*log(m))的题目,所以在哈尔滨TLE两次就放弃了,可谓经验不足;所以也是我自己的代码习惯太差,明明是dijkstra的变形、我却为了代码简洁略去了d[]数组、没有考虑过实际效率的差异。

我想哈尔滨就是对我偷懒的惩罚吧。

解题转自:http://hi.baidu.com/alpc62/item/7a5cc21e05ae4f0dd1d66d15


  1. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?

  2. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的