帮助：图形竞赛问题：可能是修改后的Dijkstra或其他替代算法

我正在尝试做关于图表的比赛练习：

XPTO是一个勇敢的冒险家（对他自己的好处来说有点过于苛刻），无论多么荒凉，他都吹嘘探索宇宙的每个角落。 事实上，他并没有访问人们可以轻松居住的行星，他更喜欢那些只有一个疯子才会有充分理由去的地方（例如数百万的学分）。 他的最新攻击是试图在Proxima III中生存。 问题在于Proxima III遭受高腐蚀性酸的风暴，这些酸会破坏一切，包括专门设计用于抵抗腐蚀的太空服。

我们勇敢的探险家被困在这些风暴之中的一个长方形区域。 幸运的是，他有一种仪器能够测量每个扇区上酸的精确浓度以及它对太空服的损害程度。 现在，他只需要知道他是否能逃脱风暴。 问题

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

你的任务是找到出口部门，达到它所需的步数以及他的衣服离开矩形区域时的能量。 选择的逃生路线应该是最安全的（即，他的宇航服将受损最少）。 请注意，如果他的西装的能量达到零，XPTO将会消亡。

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

约束0 <E≤30000套装的起始能量
0≤W≤500矩形的宽度
0≤H≤500矩形的高度
0 <X <W起始X位置
0 <Y <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

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

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

你的想法听起来不错 – 顺其自然。

顺便说一句，在处理这些问题时，请尝试自己完成实现。 简单地看一下其他人的实现很少有帮助。 如果需要，请求有关算法的帮助，但请自行实施。

Answer 2

您不必像对待任何非常规转换（减去而不是添加等）来处理此问题。

从一个节点到另一个节点的最短路径是最小化沿途的整体伤害的路径，无论这个旅程是否会杀死你。

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

如果你坚持一旦你知道你肯定无法到达EXIT就修剪搜索，那么在上述实现之后添加它是微不足道的：因为你在Dijkstra搜索中扩展你的搜索范围，甚至去了下一个最近的节点从你杀死扩展，然后其他搜索空间也将，所以你可以只是中止和Goodbye cruel world! 。

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

• 所有边缘节点都有一个指向EXIT的边缘; 这些边的权重为0
• 所有相邻（非对角线）节点在它们之间具有有向边
  • 从节点n1到n2 ，边缘的权重（即从n1行进到n2的成本损失）是停留在节点n2处的损坏（让我们称之为damageAt[n2] ，你从输入中的D矩阵得到） 。

因此，从START到EXIT必须维持的最小损伤总数是damageAt[START] + costOf(shortestPathBetween(START, EXIT)) 。

总之，这种方法：

• 只需要标准的Dijkstra实现
• 只需要很小的修改就可以添加修剪
• 只需要从输入网格到有向图的非常简单的转换