algorithm - 二维网格上从 (0,0) 到 (N,N) 的最小成本路径

Question

我有一个二维网格的问题，你试图找到从 (0, 0) 到 (N, N) 的最短路径，其中 1 < N < 10^9。还有 P (1 < P < 10^5) 快捷方式，可以从 (x1, y1) 跳转到 (x2, y2)。

旅行时，您只能向上或向右走。同样，快捷方式永远不会将您向下或向左移动。

示例案例:
你在 (0, 0) 并试图到达 (3, 3)。
有两种快捷方式:一种将您从 (0, 1) 移动到 (0, 2)，一种将您从 (1, 2) 移动到 (2, 3)。

最好的路径是:

从 (0,0) 移动到 (0,1)(1 个单位)。
(0,2) 的快捷方式。
从 (0,2) 移动到 (1,2)(1 个单位)。
(2,3) 的快捷方式。
从 (2,3) 移动到 (3,3)(1 个单位)。

所以总长度将为 3 个单位。

时间范围也是2秒。

编辑 1:我有使用动态规划的想法，做一个成本矩阵。矩阵[i][j] = 到达路径的总成本 (i, j)。然而，网格很大，矩阵有 10^18 个槽，这太大了，不适合时间框架。

编辑 2:我的下一个想法是使用 Dijkstra 算法；简单地将结束、开始和快捷方式设为图中的所有节点。然而，这变成了一个 O(N^2) 解决方案(最多有 10^10 条边!)

编辑 3:我想出了另一个 O(N^2) 解决方案。基本上，您会根据它们与原点的距离对所有快捷方式进行排序。然后，通过遍历您已经处理的所有快捷方式，您将找到每个快捷方式的最短路径。您会找到 (distTo(each Shortcut) + manhattan_distance(each_shortcut, current shortcut)) 的最小值。最后，您将处理 (N, N) 点，就好像它是找到最终解决方案的捷径一样。

但是，这仍然太慢 - 有没有办法进一步优化我的解决方案或更好的解决方案？

Answer 1

让我们注意，我们可以在常量时间 abs(a.x - b.x) + abs(a.y - b.y) 中计算从 A 点到 B 点的距离。我们可以通过它的协调对所有点进行排序。在我们运行类似 dp -> dist 之类的东西之后，点 x 将是来自门户的最小 dist 分数 i.x <= x.x && i.y <= x.x其中 i 是门户的导出，+ dist 从导出到点 x。 (仅考虑 x 如果它是数组的入口或结尾)。如果我们将 x 视为我们的第二个 for 循环，如果该点在 x 坐标上的坐标得分最差，我们还需要删除先前考虑的点，并用一个新的“虚拟”点替换它，该点得分最高。