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 条特殊道路以代价 costi 从 (x1i, y1i) 到 (x2i, y2i) 。你可以使用每条特殊道路任意次。

返回从 (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

示例 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

约束条件：

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

解题思路

这是一个典型的最短路径问题。根据题目提示，我们只需要考虑起点、终点以及所有特殊道路的起点和终点作为图中的节点。

核心思路：

  1. 建图：将起点、终点以及所有特殊道路的起点和终点作为图的节点
  2. 连边：
    • 任意两点之间都有一条边，权重为曼哈顿距离
    • 特殊道路提供额外的有向边，权重为给定的 cost
  3. 最短路径：使用 Dijkstra 算法求从起点到终点的最短路径

算法步骤：

  1. 收集所有关键点：起点、终点、特殊道路的起点和终点
  2. 对每个点，维护从起点到该点的最短距离
  3. 使用优先队列进行 Dijkstra 算法：
    • 每次取出当前距离最小的点
    • 更新其邻接点的距离
    • 对于每个点，可以通过曼哈顿距离到达任意其他点，也可以通过特殊道路到达指定点

优化要点：

  • 只有当特殊道路的代价小于曼哈顿距离时才有意义
  • 使用坐标压缩，避免处理过多无用的中间点

代码实现

class Solution {
public:
    int minimumCost(vector<int>& start, vector<int>& target, vector<vector<int>>& specialRoads) {
        // 收集所有关键点
        set<pair<int, int>> points;
        points.insert({start[0], start[1]});
        points.insert({target[0], target[1]});
        
        for (auto& road : specialRoads) {
            points.insert({road[0], road[1]});
            points.insert({road[2], road[3]});
        }
        
        // 点到索引的映射
        vector<pair<int, int>> pointList(points.begin(), points.end());
        map<pair<int, int>, int> pointToIndex;
        for (int i = 0; i < pointList.size(); i++) {
            pointToIndex[pointList[i]] = i;
        }
        
        int n = pointList.size();
        int startIdx = pointToIndex[{start[0], start[1]}];
        int targetIdx = pointToIndex[{target[0], target[1]}];
        
        // Dijkstra算法
        vector<int> dist(n, INT_MAX);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
        
        dist[startIdx] = 0;
        pq.push({0, startIdx});
        
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            
            if (d > dist[u]) continue;
            
            auto [x1, y1] = pointList[u];
            
            // 通过曼哈顿距离到达其他所有点
            for (int v = 0; v < n; v++) {
                if (u == v) continue;
                auto [x2, y2] = pointList[v];
                int cost = abs(x2 - x1) + abs(y2 - y1);
                if (dist[u] + cost < dist[v]) {
                    dist[v] = dist[u] + cost;
                    pq.push({dist[v], v});
                }
            }
            
            // 通过特殊道路
            for (auto& road : specialRoads) {
                if (road[0] == x1 && road[1] == y1) {
                    int v = pointToIndex[{road[2], road[3]}];
                    if (dist[u] + road[4] < dist[v]) {
                        dist[v] = dist[u] + road[4];
                        pq.push({dist[v], v});
                    }
                }
            }
        }
        
        return dist[targetIdx];
    }
};

class Solution:
    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:
        import heapq
        
        # 收集所有关键点
        points = set()
        points.add((start[0], start[1]))
        points.add((target[0], target[1]))
        
        for road in specialRoads:
            points.add((road[0], road[1]))
            points.add((road[2], road[3]))
        
        # 点到索引的映射
        point_list = list(points)
        point_to_index = {point: i for i, point in enumerate(point_list)}
        
        n = len(point_list)
        start_idx = point_to_index[(start[0], start[1])]
        target_idx = point_to_index[(target[0], target[1])]
        
        # Dijkstra算法
        dist = [float('inf')] * n
        dist[start_idx] = 0
        pq = [(0, start_idx)]
        
        while pq:
            d, u = heapq.heappop(pq)
            
            if d > dist[u]:
                continue
            
            x1, y1 = point_list[u]
            
            # 通过曼哈顿距离到达其他所有点
            for v in range(n):
                if u == v:
                    continue
                x2, y2 = point_list[v]
                cost = abs(x2 - x1) + abs(y2 - y1)
                if dist[u] + cost < dist[v]:
                    dist[v] = dist[u] + cost
                    heapq.heappush(pq, (dist[v], v))
            
            # 通过特殊道路
            for road in specialRoads:
                if road[0] == x1 and road[1] == y1:
                    v = point_to_index[(road[2], road[3])]
                    if dist[u] + road[4] < dist[v]:
                        dist[v] = dist[u] + road[4]
                        heapq.heappush(pq, (dist[v], v))
        
        return dist[target_idx]

public class Solution {
    public int MinimumCost(int[] start, int[] target, int[][] specialRoads) {
        // 收集所有关键点
        var points = new HashSet<(int, int)>();
        points.Add((start[0], start[1]));
        points.Add((target[0], target[1]));
        
        foreach (var road in specialRoads) {
            points.Add((road[0], road[1]));
            points.Add((road[2], road[3]));
        }
        
        // 点到索引的映射
        var pointList = points.ToList();
        var pointToIndex = new Dictionary<(int, int), int>();
        for (int i = 0; i < pointList.Count; i++) {
            pointToIndex[pointList[i]] = i;
        }
        
        int n = pointList.Count;
        int startIdx = pointToIndex[(start[0], start[1])];
        int targetIdx = pointToIndex[(target[0], target[1])];
        
        // Dijkstra算法
        var dist = new int[n];
        Array.Fill(dist, int.MaxValue);
        dist[startIdx] = 0;
        
        var pq = new PriorityQueue<int, int>();
        pq.Enqueue(startIdx, 0);
        
        while (pq.Count > 0) {
            int u = pq.Dequeue();
            
            var (x1, y1) = pointList[u];
            
            // 通过曼哈顿距离到达其他所有点
            for (int v = 0; v < n; v++) {
                if (u == v) continue;
                var (x2, y2) = pointList[v];
                int cost = Math.Abs(x2 - x1) + Math.Abs(y2 - y1);
                if (dist[u] != int.MaxValue && dist[u] + cost < dist[v]) {
                    dist[v] = dist[u] + cost;
                    pq.Enqueue(v, dist[v]);
                }
            }
            
            // 通过特殊道路
            foreach (var road in specialRoads) {
                if (road[0] == x1 && road[1] == y1) {
                    int v = pointToIndex[(road[2], road[3])];
                    if (dist[u] != int.MaxValue && dist[u] + road[4] < dist[v]) {
                        dist[v] = dist[u] + road[4];
                        pq.Enqueue(v, dist[v]);
                    }
                }
            }
        }
        
        return dist[targetIdx];
    }
}

var minimumCost = function(start, target, specialRoads) {
    const manhattanDistance = (p1, p2) => Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);
    
    // Create a list of all points (start, target, and all special road endpoints)
    const points = new Set();
    points.add(`${start[0]},${start[1]}`);
    points.add(`${target[0]},${target[1]}`);
    
    for (const road of specialRoads) {
        points.add(`${road[0]},${road[1]}`);
        points.add(`${road[2]},${road[3]}`);
    }
    
    const pointsList = Array.from(points).map(p => p.split(',').map(Number));
    const n = pointsList.length;
    
    // Find indices
    const startIdx = pointsList.findIndex(p => p[0] === start[0] && p[1] === start[1]);
    const targetIdx = pointsList.findIndex(p => p[0] === target[0] && p[1] === target[1]);
    
    // Build adjacency matrix with Manhattan distances
    const dist = Array(n).fill().map(() => Array(n).fill(Infinity));
    
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (i === j) {
                dist[i][j] = 0;
            } else {
                dist[i][j] = manhattanDistance(pointsList[i], pointsList[j]);
            }
        }
    }
    
    // Add special roads
    for (const road of specialRoads) {
        const fromIdx = pointsList.findIndex(p => p[0] === road[0] && p[1] === road[1]);
        const toIdx = pointsList.findIndex(p => p[0] === road[2] && p[1] === road[3]);
        dist[fromIdx][toIdx] = Math.min(dist[fromIdx][toIdx], road[4]);
    }
    
    // Floyd-Warshall
    for (let k = 0; k < n; k++) {
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    
    return dist[startIdx][targetIdx];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

指标复杂度
时间-
空间-

相关题目