What is the Minimum Cost of a Path With Special Roads problem?

The problem asks you to find the minimum cost path between a start and target point in a 2D grid, considering both direct moves and special roads with defined costs.

How does the special road affect the cost calculation?

Special roads provide a cost-effective way to travel between points in the grid. These roads are factored into the minimum cost path calculation alongside the direct distance.

Why should we only consider start, target, and special road endpoints?

It has been proven that optimal paths only require considering these key points, as any other paths would incur higher costs or be redundant.

What algorithm is most suitable for solving this problem?

Dijkstra’s algorithm is most suitable as it efficiently handles the shortest path in graphs with varying edge weights, especially when combined with a priority queue.

How can GhostInterview assist in solving this problem?

GhostInterview provides step-by-step guidance on applying graph algorithms, optimizing your solution, and avoiding common pitfalls like inefficient path selection.

#2662

Medium

auto_awesome堆

LeetCode 题解工作台

前往目标的最小代价

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

数组图堆（优先队列）最短路径

题目描述

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

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

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

返回从 (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) 到 (1,2) 花费为 |1 - 1| + |2 - 1| = 1。
(1,2) 到 (3,3)。使用 specialRoads[0] 花费为 2。
(3,3) 到 (3,4) 花费为 |3 - 3| + |4 - 3| = 1。
(3,4) 到 (4,5)。使用 specialRoads[1] 花费为 1。

所以总花费是 1 + 2 + 1 + 1 = 5。

示例 2：

输入：start = [3,2], target = [5,7], specialRoads = [[5,7,3,2,1],[3,2,3,4,4],[3,3,5,5,5],[3,4,5,6,6]]

输出：7

解释：

不使用任何特殊路径，直接从开始到结束位置是最优的，花费为 |5 - 3| + |7 - 2| = 7。

注意 specialRoads[0] 直接从 (5,7) 到 (3,2)。

示例 3：

输入：start = [1,1], target = [10,4], specialRoads = [[4,2,1,1,3],[1,2,7,4,4],[10,3,6,1,2],[6,1,1,2,3]]

输出：8

解释：

(1,1) 到 (1,2) 花费为 |1 - 1| + |2 - 1| = 1。
(1,2) 到 (7,4)。使用 specialRoads[1] 花费为 4。
(7,4) 到 (10,4) 花费为 |10 - 7| + |4 - 4| = 3。

提示：

start.length == target.length == 2
1 <= startX <= targetX <= 10⁵
1 <= startY <= targetY <= 10⁵
1 <= specialRoads.length <= 200
specialRoads[i].length == 5
startX <= x1_i, x2_i <= targetX
startY <= y1_i, y2_i <= targetY
1 <= cost_i <= 10⁵

lightbulb

解题思路

方法一：Dijkstra

我们可以发现，对于访问到的每个坐标点 $(x, y)$ ，假设从起点到 $(x, y)$ 的最小代价为 $d$ 。如果选择直接移动到 $(targetX, targetY)$ ，那么总代价就是 $d + |x - targetX| + |y - targetY|$ 。如果选择经过某条特殊路径 $(x_1, y_1) \rightarrow (x_2, y_2)$ ，那么我们需要可以花费 $|x - x_1| + |y - y_1| + cost$ 的代价，从 $(x, y)$ 移动到 $(x_2, y_2)$ 。

因此，我们可以使用 Dijkstra 算法求出从起点到所有点的最小代价，然后从中选择最小的那个。

我们定义一个优先队列 $q$ ，队列中的每一个元素是一个三元组 $(d, x, y)$ ，表示从起点到 $(x, y)$ 的最小代价为 $d$ 。初始时，我们将 $(0, startX, startY)$ 加入队列中。

在每一步中，我们取出队首元素 $(d, x, y)$ ，此时我们可以更新答案，即 $ans = \min(ans, d + dist(x, y, targetX, targetY))$ 。然后我们枚举所有的特殊路径 $(x_1, y_1) \rightarrow (x_2, y_2)$ ，将 $(d + dist(x, y, x_1, y_1) + cost, x_2, y_2)$ 加入队列中。

最后当队列为空时，我们就可以得到答案。

时间复杂度 $O(n^2 \times \log n)$ ，空间复杂度 $O(n^2)$ 。其中 $n$ 是特殊路径的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def minimumCost(
        self, start: List[int], target: List[int], specialRoads: List[List[int]]
    ) -> int:
        def dist(x1: int, y1: int, x2: int, y2: int) -> int:
            return abs(x1 - x2) + abs(y1 - y2)

        q = [(0, start[0], start[1])]
        vis = set()
        ans = inf
        while q:
            d, x, y = heappop(q)
            if (x, y) in vis:
                continue
            vis.add((x, y))
            ans = min(ans, d + dist(x, y, *target))
            for x1, y1, x2, y2, cost in specialRoads:
                heappush(q, (d + dist(x, y, x1, y1) + cost, x2, y2))
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Evaluating how the candidate handles pathfinding in a graph with variable edge costs.
question_mark
How the candidate optimizes the graph search based on the start and target points.
question_mark
Whether the candidate can apply Dijkstra's algorithm correctly with the given constraints.

warning

常见陷阱

外企场景

error
Not reducing the problem space by only considering key points (start, target, special road endpoints).
error
Ignoring the optimization of pathfinding using a priority queue, leading to inefficient solutions.
error
Failing to handle edge cases such as when no special roads are useful or when a direct path is optimal.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider adding more special roads with varied costs to increase the complexity of the problem.
arrow_right_alt
Modify the problem to allow for multiple target positions and find the shortest path to any of them.
arrow_right_alt
Allow bidirectional special roads, which would require additional logic to handle the reverse direction.

help

常见问题

外企场景

继续练习

#2577 在网格图中访问一个格子的最少时间 #2290 到达角落需要移除障碍物的最小数目 #3112 访问消失节点的最少时间