帮助：图形竞赛题：也许是改进Dijkstra或其他替代算法

Question

我试图做这个比赛锻炼一下图：

XPTO是一个勇敢的冒险家（有点太temerarious为自己的好），谁拥有关于探索宇宙的每一个角落，无论多么不友善。事实上，他并没有访问人们可以轻松生活的行星，他更喜欢那些只有疯子才会有很好理由（例如数百万信用点）的行星。他最近的一次尝试是在Proxima III中生存。问题是Proxima III遭受高度腐蚀性酸的风暴破坏了一切，包括特别设计用于承受腐蚀的太空服。

我们勇敢的探险家在这些风暴中的一个矩形区域被捕。幸运的是，他有一种能够测量每个区域酸的确切浓度以及它对太空服造成多大伤害的仪器。现在，他只需要知道他是否能躲过风暴。 问题

问题包括找到一个逃生路线，这将允许XPTO逃离有毒风暴。你会获得太空服的初始能量，矩形区域的大小以及宇航服站在每个区域时受到的伤害。

您的任务是找到出口扇区，达到它的步数以及他的服装在离开矩形区域时的能量数量。选择的逃生路线应该是最安全的路线（即其太空服损坏最少的那条路线）。注意，如果XPTO的能量达到零，XPTO将会消亡。

如果有多种可能的解决方案，请选择使用最少步骤数的解决方案。如果至少有两个扇区具有相同步数（X1，Y1）和（X2，Y2），则选择第一个，如果X1 < X2或者X1 = X2和Y1 < Y2。

约束Ë≤30000衣服的起动能量
0≤w ^≤500的矩形的宽度
0≤ħ≤500矩形的高度
X < W上的起始X位置
ÿ < H起始Y位置
0≤D≤10000各区段持续受损

输入

给出的第一个数字是测试用例的数量。每个案例将包括一条与整数E，X和Y的线。下面的线将具有整数W和H.下面的线将保持包含太空服在对应扇区中遭受损伤D的矩阵。请注意，对于计算机极客来说，情况经常如此，（1,1）对应于左上角。

输出

如果有一个解决方案，输出将剩余能量，出口部门的X和Y坐标的，这将导致Rodericus安全路由的步数。如果没有解决办法，那句再见残酷的世界！将被写入。

采样输入

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，其中节点之间的距离是衣服的能量（和我们必须减去它，而不是像距离正常那样总结），并且步骤是沿着路径进行的......步骤。与bester二项式（能源，num_Steps）pos是我们的“出路”。

重要提示：XPTO显然不能在对角线上移动，所以我们必须删除这些情况。

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

可能有人请帮我想这个跟一些代码，或者至少，想法？

我完全错了吗？

Answer 1

你不必像你说的那样用任何非常规的转换来对待它（减去而不是增加等）。

从一个节点到另一个节点的最短路径是最大限度地减少对途中的总体伤害，无论这个旅程是否会杀死你。

只需找到从START到EXIT的最短路径，按照通常的Dijkstra方法总结边权重，然后然后考虑这个最短路径对于给定的套装功率是否可行。如果不是，那么Goodbye cruel world!。

如果你坚持修剪搜索，一旦你知道你可以绝对未到达出口，那么上面的实施后，将它添加很简单：当你正在扩大在Dijkstra算法的搜索搜索地平线，如果连去下一个最接近的节点来杀死你，然后其余的搜索空间也会，所以你可以放弃和Goodbye cruel world!。

至于图本身，概念上这就是你想要的。有向图的顶点由网格中的所有节点以及一个人为的EXIT节点组成。

• 所有边缘节点都有EXIT的有向边;这些边缘的权重为0
• 所有相邻（非对角）节点已将他们
  • 之间的有向边从节点n1到n2，该边的权重（即，行进从n1到n2成本损坏）是留在节点n2（我们称之为damageAt[n2]，您从输入中的D矩阵中获得）造成的损害。一个人必须保持去从开始到退出损坏的

所以最低总额为damageAt[START] + costOf(shortestPathBetween(START, EXIT))。

总之，这种方法：

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

Answer 2

由于这是一个比赛问题，我会给出一个小提示：

在这个例子中，它是节点有权重，而不是边缘。将这样的图转换成通常的类型的一种方式是用两个节点替换每个节点，即节点in和节点out，以及从in到out的有向边，其中权重等于原始节点的权重。然后，对于原始图中的每个有向边，将从1的out节点到下一个的in节点的有向边放置。

你的想法听起来不错 - 走吧。

顺便说一下，在处理这些问题时，请尝试为自己制定实施方案。它很少有助于简单地看到别人的实施。如果您需要，请求算法帮助，但自己实现它。