cra*_*cra 5 language-agnostic algorithm graph dynamic shortest-path
我有一个 2D 网格问题，您试图找到从 (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) 点，就好像它是找到最终解决方案的捷径一样。
但是，这仍然太慢 - 有没有办法进一步优化我的解决方案或更好的解决方案？
我们注意到，我们可以在 const 时间内计算从 A 点到 B 点的距离：abs(ax - bx) + abs(ay - by)。我们可以通过协调性对所有点进行排序。在我们对点 x 运行类似 dp -> dist 的操作之后，将是来自门户的最小距离分数，其中i.x <= x.x && i.y <= x.xi 是门户的出口，+ 从出口到点 x 的距离。（如果 x 是数组的入口或末尾，则仅考虑 x）。如果我们将 x 视为第二个 for 循环，则如果该点在 x 坐标上的坐标中得分最差，我们还需要删除先前考虑的点并将其替换为具有最佳得分的新“虚拟”点。