前往目标的最小代价

标签: 图 数组 最短路 堆（优先队列）

难度: Medium

给你一个数组 start ，其中 start = [startX, startY] 表示你的初始位置位于二维空间上的 (startX, startY) 。另给你一个数组 target ，其中 target = [targetX, targetY] 表示你的目标位置 (targetX, targetY) 。

从位置 (x1, y1) 到空间中任一其他位置 (x2, y2) 的代价是 |x2 - x1| + |y2 - y1| 。

给你一个二维数组 specialRoads ，表示空间中存在的一些特殊路径。其中 specialRoads[i] = [x1i, y1i, x2i, y2i, costi] 表示第 i 条特殊路径可以从 (x1i, y1i) 到 (x2i, y2i) ，但成本等于 costi 。你可以使用每条特殊路径任意次数。

返回从 (startX, startY) 到 (targetX, targetY) 所需的最小代价。

示例 1：

输入：start = [1,1], target = [4,5], specialRoads = [[1,2,3,3,2],[3,4,4,5,1]]
输出：5
解释：从 (1,1) 到 (4,5) 的最优路径如下：
- (1,1) -> (1,2) ，移动的代价是 |1 - 1| + |2 - 1| = 1 。
- (1,2) -> (3,3) ，移动使用第一条特殊路径，代价是 2 。
- (3,3) -> (3,4) ，移动的代价是 |3 - 3| + |4 - 3| = 1.
- (3,4) -> (4,5) ，移动使用第二条特殊路径，代价是 1 。
总代价是 1 + 2 + 1 + 1 = 5 。
可以证明无法以小于 5 的代价完成从 (1,1) 到 (4,5) 。

示例 2：

输入：start = [3,2], target = [5,7], specialRoads = [[3,2,3,4,4],[3,3,5,5,5],[3,4,5,6,6]]
输出：7
解释：最优路径是不使用任何特殊路径，直接以 |5 - 3| + |7 - 2| = 7 的代价从初始位置到达目标位置。

提示：

  • start.length == target.length == 2
  • 1 <= startX <= targetX <= 105
  • 1 <= startY <= targetY <= 105
  • 1 <= specialRoads.length <= 200
  • specialRoads[i].length == 5
  • startX <= x1i, x2i <= targetX
  • startY <= y1i, y2i <= targetY
  • 1 <= costi <= 105

Submission

运行时间: 74 ms

内存: 16.2 MB

class Solution:
    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:
        t = tuple(target)
        dist = defaultdict(lambda:inf)
        dist[tuple(start)] = 0
        vis = set()
        while True:
            v, dv = None, -1
            for p, d in dist.items():
                if p not in vis and (dv < 0 or d < dv):
                    v, dv = p, d
            if v == t :
                return dv
            vis.add(v)
            vx, vy = v
            dist[t] = min(dist[t], dv + t[0] - vx + t[1] - vy)
            for x1, y1, x2, y2, cost in specialRoads:
                w = (x2, y2)
                dist[w] = min(dist[w], dv + abs(x1 - vx) + abs(y1 - vy) + cost)

Explain

该题解采用了类似于Dijkstra算法的策略来解决从初始位置到目标位置的最小代价问题。首先，初始化一个距离字典`dist`，其中初始位置的距离设为0，其余位置距离为无穷大。使用一个集合`vis`来记录已经访问过的点。在算法执行过程中，每次从未访问的点中选择一个当前距离最小的点作为当前处理的点。如果该点为目标点，则返回其对应的距离值。对选出的点进行扩展，更新其通过普通移动或特殊路径到其他点的距离。普通移动的代价为坐标差的绝对值和，特殊路径的代价为在路径起点的代价加上特定成本`costi`。

时间复杂度: O(n^2 + nm)

空间复杂度: O(n)

class Solution:
    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:
        t = tuple(target)
        dist = defaultdict(lambda:inf) # 初始化距离字典, 所有点距离为无穷大
        dist[tuple(start)] = 0 # 开始点距离设为0
        vis = set() # 访问集合
        while True:
            v, dv = None, -1
            for p, d in dist.items():
                if p not in vis and (dv < 0 or d < dv):
                    v, dv = p, d # 选择未访问且距离最小的点
            if v == t :
                return dv # 如果是目标点，返回当前距离
            vis.add(v) # 标记为已访问
            vx, vy = v
            dist[t] = min(dist[t], dv + t[0] - vx + t[1] - vy) # 更新到目标点的距离
            for x1, y1, x2, y2, cost in specialRoads:
                w = (x2, y2)
                dist[w] = min(dist[w], dv + abs(x1 - vx) + abs(y1 - vy) + cost) # 更新通过特殊路径到达点的距离

Explore

在Dijkstra算法中，使用优先队列可以有效地从未访问的节点中快速找到当前距离最小的节点。如果不使用优先队列，如题解所示，每次寻找最小距离节点需要遍历所有节点，复杂度是O(n)。这种遍历方式在节点数量较多时会显著增加计算时间，导致整体算法效率下降，尤其是在稀疏图中，使用优先队列可以将时间复杂度降低到O((V+E)logV)，其中V是节点数，E是边数。

题解中并没有特别说明如何避免特殊路径的重复使用或循环引用。在实际实现中，可以通过在访问集合`vis`中记录已经处理过的节点来避免重复处理。此外，若存在循环引用的可能，需要设计额外的逻辑来检测和阻止这种情况，例如使用一个字典来记录每个节点的访问次数并设定阈值，或者在发现循环时终止算法。

题解中的`abs(x1 - vx) + abs(y1 - vy)`表示从当前节点v到特殊路径起点(x1, y1)的曼哈顿距离。这个距离加上特殊路径的成本`cost`和当前点到v的最短距离`dv`合在一起，才是从起始点经过v到达特殊路径终点w的总代价。因此，这里的表达式是正确的，考虑到了从当前节点到特殊路径起点的移动成本。

题解中通过遍历`specialRoads`数组，对每条特殊路径进行处理。对于数组中的每个元素，提取起点(x1, y1)和终点(x2, y2)的坐标以及路径的特定成本`cost`。然后，基于当前节点v的已知最短距离dv，计算到达特殊路径终点w的可能最短距离，并使用`min`函数更新距离字典`dist`中w点的值。这种方法确保了每次算法只会试图优化到达每个节点的最短距离。