我有一个 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 条边！）
编辑 …