2014
01-26

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

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，障碍物#，漩涡*

1.普通航行一格

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

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

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

—–

x——横坐标

y——纵坐标

oil——加速次数

unt——进入漩涡次数

t——路过的格子数

step——回合数

—–

—–

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堆很难写、很罕见。

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
不知道题目例子是怎么得出来的