我对2D网格有问题，您正在尝试查找从（0，0）到（N，N）的最短路径，其中1 旅行时，您只能向上或向右行走。同样，快捷方式也永远不会将您向下或向左移动。 示例：您位于（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（每个快捷方式）+ manhattan_distance（每个快捷方式，当前快捷方式））的最小值。最后，您将处理（N，N）点，好像这是找到最终解决方案的捷径。 但是，这仍然太慢-有没有办法进一步优化我的解决方案或更好的解决方案？
请注意，我们可以以常数时间abs（a.x-b.x）+ abs（a.y-b.y）计算从A点到B点的距离。我们可以通过其协调对所有点进行排序。在我们对点x运行类似dp-> dist的操作之后，将是i.x <= x.x && i.y <= x.x处门户的最小dist得分，其中i是门户的出口，+出口到点x的dist。 （如果x是数组的入口或结尾，则仅考虑它）。如果我们将x视为第二个for循环，则如果该点在x坐标上的坐标得分最差，我们还需要删除先前考虑的点，并用得分最高的新“虚拟”点替换它。
使用顶点作为起点，终点和每个快捷方式的图形。