我试着做一下图表本次比赛的锻炼：

I'm trying to do this contest exercise about graphs:

XPTO是一个勇敢的冒险家（有点太temerarious为自己的好），谁拥有约探索宇宙的每一个角落，无论多么恶劣。事实上，他并没有参观，人们可以很容易地生活在行星，他prefers那些只有疯子才会有一个很好的理由（几百万学分的实例）去。他最新的漏洞正试图在比邻三生存。问题是，比邻三从高腐蚀性酸的风暴会摧毁一切，包括宇航服是被特别设计，以抵御腐蚀受损。

XPTO is an intrepid adventurer (a little too temerarious for his own good) who boasts about exploring every corner of the universe, no matter how inhospitable. In fact, he doesn't visit the planets where people can easily live in, he prefers those where only a madman would go with a very good reason (several millions of credits for instance). His latest exploit is trying to survive in Proxima III. The problem is that Proxima III suffers from storms of highly corrosive acids that destroy everything, including spacesuits that were especially designed to withstand corrosion.

我们的勇敢的探险家陷入了一个矩形区域，在这些风暴之一的中间。幸运的是，他有一个仪器能测量每个部门和造成多大的损害它自己的宇航服酸的准确浓度。现在，他只需要看看他能逃过难关。 问题

Our intrepid explorer was caught in a rectangular area in the middle of one of these storms. Fortunately, he has an instrument that is capable of measuring the exact concentration of acid on each sector and how much damage it does to his spacesuit. Now, he only needs to find out if he can escape the storm. Problem

问题包括寻找一条退路，让XPTO逃脱有毒风暴。你给出宇航服的初始能量，该矩形区域的大小和站在每个扇区而宇航服将遭受损害。

The problem consists of finding an escape route that will allow XPTO to escape the noxious storm. You are given the initial energy of the spacesuit, the size of the rectangular area and the damage that the spacesuit will suffer while standing in each sector.

你的任务是找到出口行业中，要达到这步数和量能，当他离开的矩形区域他的衣服都会有。选择的逃跑路线应该是最安全的（即一，他的宇航服将是最损坏）。注意，如果他的西装的能量达到零XPTO会灭亡。

Your task is to find the exit sector, the number of steps necessary to reach it and the amount of energy his suit will have when he leaves the rectangular area. The escape route chosen should be the safest one (i.e., the one where his spacesuit will be the least damaged). Notice that XPTO will perish if the energy of his suit reaches zero.

在情况下，有一个以上的可能的解决方案中，选择，使用最少数量的步骤之一。如果有至少两个扇区与相同的步骤编号（X1，Y1）和（X2，Y2），则选择第一个，如果X1＆其中; X2或如果X1 = X2和Y1，其中; Y2。

In case there are more than one possible solutions, choose the one that uses the least number of steps. If there are at least two sectors with the same number of steps (X1, Y1) and (X2, Y2) then choose the first if X1 < X2 or if X1 = X2 and Y1 < Y2.

约束 0℃下Ë≤30000西服的起始能量 0≤W¯¯≤500矩形的宽度 0≤^ h≤500矩形的高度 0℃下X - LT; W上的起始X位置 0℃下Y'LT;小时起始Y位置 0≤ð≤10000维持在每个扇区的损坏

Constraints 0 < E ≤ 30000 the suit's starting energy 0 ≤ W ≤ 500 the rectangle's width 0 ≤ H ≤ 500 rectangle's height 0 < X < W the starting X position 0 < Y < H the starting Y position 0 ≤ D ≤ 10000 the damage sustained in each sector

输入

给出的第一个数字是测试用例的数量。每一种情况下将包括与整数E，X和Y中每一行的下面一行将具有整数W和H的下列行将于含有损害D中的太空服将遭受的同时在相应的扇区的矩阵。请注意，如通常用于计算机爱好者的情况下，（1,1）相应于左上角。

The first number given is the number of test cases. Each case will consist of a line with the integers E, X and Y. The following line will have the integers W and H. The following lines will hold the matrix containing the damage D the spacesuit will suffer whilst in the corresponding sector. Notice that, as is often the case for computer geeks, (1,1) corresponds to the upper left corner.

输出

如果有一个解决方案，输出将剩余的能量，出射扇区的X和Y坐标和步骤，这将导致Rodericus到安全的路线的数量。如果没有解决，那句再见残酷的世界！将被写入。

If there is a solution, the output will be the remaining energy, the exit sector's X and Y coordinates and the number of steps of the route that will lead Rodericus to safety. In case there is no solution, the phrase Goodbye cruel world! will be written.

采样输入

3
40 3 3  
7 8  
12 11 12 11  3 12 12  
12 11 11 12  2  1 13  
11 11 12  2 13  2 14  
10 11 13  3  2  1 12 
10 11 13 13 11 12 13 
12 12 11 13 11 13 12  
13 12 12 11 11 11 11  
13 13 10 10 13 11 12  
8 3 4  
7 6 
4  3  3  2  2  3  2  
2  5  2  2  2  3  3  
2  1  2  2  3  2  2  
4  3  3  2  2  4  1  
3  1  4  3  2  3  1  
2  2  3  3  0  3  4  
10 3 4  
7 6  
3  3  1  2  2  1  0 
2  2  2  4  2  2  5  
2  2  1  3  0  2  2  
2  2  1  3  3  4  2  
3  4  4  3  1  1  3  
1  2  2  4  2  2  1 

示例输出

12 5 1 8  
Goodbye cruel world!  
5 1 4 2

基本上，我认为我们必须做一个改进Dijkstra，其中节点之间的距离是西服的能量（我们必须减去舒米恩像正常使用距离它代替）和步骤是... .steps沿路径进行。与贝斯特二项式的POS（能源，num_Steps）是我们的出路。

Basically, I think we have to do a modified Dijkstra, in which the distance between nodes is the suit's energy (and we have to subtract it instead of suming up like is normal with distances) and the steps are the ....steps made along the path. The pos with the bester binomial (Energy,num_Steps) is our "way out".

重要提示：XPTO显然不能在对角线移动，所以我们要切出此情况下

Important : XPTO obviously can't move in diagonals, so we have to cut out this cases.

我有很多想法，但我有这样一个实现他们的问题...

I have many ideas, but I have such a problem implementing them...

可能有人请帮我想这个与一些code，或者至少，想法？

Could someone please help me thinking about this with some code or, at least, ideas?

我是完全错误的？

推荐答案

您不必把这个与任何非常规的转换，像你说的（扣除，而不是增加，等等）。

You don't have to treat this with any unconventional conversions like you said (subtracting instead of adding, etc).

的最短路径从一个节点到另一个节点是一个最小化到沿途的衣服总伤害，不管这次旅程是否会杀了你。

The shortest path from one node to another is one that minimizes the total damage to the suit along the way, regardless of whether or not this journey will kill you.

只要找到最短路径从开始到退出，总结边的权重像通常那样Dijkstra算法的方法，和然后的考虑，如果这最短路径对给定的西装功率是可行的。如果不是，那么再见残酷的世界！。

Just find the shortest path from START to EXIT, summing up edge weights as is usual Dijkstra approach, and then consider if this shortest path is feasible for the given suit power. If it isn't, then Goodbye cruel world!.

如果你坚持要修剪的搜索，一旦你知道你可以的绝对的未到达出口，那么上面的实施后，将它添加很简单：当你正在扩大搜索范围的地平线在你的Dijkstra搜索，如果连去下一个最近的节点，扩大自杀死你，然后搜索空间的其余部分也将，让你可以中止和再见残酷的世界！。

If you insist on pruning the search once you know that you can definitely not reach the EXIT, then adding it after the above implementation is trivial: as you're expanding your search horizon in your Dijkstra search, if even going to the next closest node to expand from kills you, then the rest of search space also will, so you can just abort and Goodbye cruel world!.

对于图形本身，在概念上，这是你想要的。有向图的顶点由网格中的所有节点，加上人工EXIT节点

As for the graph itself, conceptually this is what you want. The vertices of the directed graph consists of all nodes in the grid, plus an artificial EXIT node.

在所有边缘节点有向边表示退出;这些边缘的权重为0 所有邻国（非对角线）节点已经指示他们之间的边缘 从节点 N1 到 N2 ，边的权重（从 N1 到 N2 ）是招致住在节点损坏 N2 （我们称之为 damageAt [N2] ，你从 D获得矩阵输入）。 All edge nodes have a directed edge to EXIT; the weight of these edges is 0 All neighboring (non-diagonal) node have directed edges between them From node n1 to n2, the weight of the edge (i.e. the cost damage of travelling from n1 to n2) is the damage incurred by staying at node n2 (let's call this damageAt[n2], which you get from D matrix in input).

伤害，人们必须保持去从开始到退出以最小的总金额 damageAt [开始] + costOf（shortestPathBetween（START，EXIT））。

So minimum total amount of damage that one must sustain to go from START to EXIT is damageAt[START] + costOf(shortestPathBetween(START, EXIT)).

总之，这种方式：

只需要标准的Dijkstra实施 仅需要很小的修改，以增加修剪 仅需要从电网输入非常简单的改造，有向图