class Solution {
public:
int minimumCost(vector<int>& start, vector<int>& target, vector<vector<int>>& specialRoads) {
}
};
2662. 前往目标的最小代价
给你一个数组 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 == 21 <= startX <= targetX <= 1051 <= startY <= targetY <= 1051 <= specialRoads.length <= 200specialRoads[i].length == 5startX <= x1i, x2i <= targetXstartY <= y1i, y2i <= targetY1 <= costi <= 105原站题解
golang 解法, 执行用时: 16 ms, 内存消耗: 4.5 MB, 提交时间: 2023-05-05 17:02:46
func minimumCost(start, target []int, specialRoads [][]int) int {
type pair struct{ x, y int }
t := pair{target[0], target[1]}
dis := make(map[pair]int, len(specialRoads)+2)
dis[t] = math.MaxInt
dis[pair{start[0], start[1]}] = 0
vis := make(map[pair]bool, len(specialRoads)+1) // 终点不用记
for {
v, dv := pair{}, -1
for p, d := range dis {
if !vis[p] && (dv < 0 || d < dv) {
v, dv = p, d
}
}
if v == t { // 到终点的最短路已确定
return dv
}
vis[v] = true
dis[t] = min(dis[t], dv+t.x-v.x+t.y-v.y) // 更新到终点的最短路
for _, r := range specialRoads {
w := pair{r[2], r[3]}
d := dv + abs(r[0]-v.x) + abs(r[1]-v.y) + r[4]
if dw, ok := dis[w]; !ok || d < dw {
dis[w] = d
}
}
}
}
func abs(x int) int { if x < 0 { return -x }; return x }
func min(a, b int) int { if b < a { return b }; return a }
java 解法, 执行用时: 29 ms, 内存消耗: 42.9 MB, 提交时间: 2023-05-05 17:02:34
class Solution {
public int minimumCost(int[] start, int[] target, int[][] specialRoads) {
long t = (long) target[0] << 32 | target[1];
var dis = new HashMap<Long, Integer>();
dis.put(t, Integer.MAX_VALUE);
dis.put((long) start[0] << 32 | start[1], 0);
var vis = new HashSet<Long>();
for (;;) {
long v = -1;
int dv = -1;
for (var e : dis.entrySet())
if (!vis.contains(e.getKey()) && (dv < 0 || e.getValue() < dv)) {
v = e.getKey();
dv = e.getValue();
}
if (v == t) return dv; // 到终点的最短路已确定
vis.add(v);
int vx = (int) (v >> 32), vy = (int) (v & Integer.MAX_VALUE);
// 更新到终点的最短路
dis.merge(t, dv + target[0] - vx + target[1] - vy, Math::min);
for (var r : specialRoads) {
int d = dv + Math.abs(r[0] - vx) + Math.abs(r[1] - vy) + r[4];
long w = (long) r[2] << 32 | r[3];
if (d < dis.getOrDefault(w, Integer.MAX_VALUE))
dis.put(w, d);
}
}
}
}
python3 解法, 执行用时: 92 ms, 内存消耗: 16.2 MB, 提交时间: 2023-05-05 17:02:20
# 朴素 Dijkstra 求最短路径
class Solution:
def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:
t = tuple(target)
dis = defaultdict(lambda: inf)
dis[tuple(start)] = 0
vis = set()
while True:
v, dv = None, -1
for p, d in dis.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
dis[t] = min(dis[t], dv + t[0] - vx + t[1] - vy) # 更新到终点的最短路
for x1, y1, x2, y2, cost in specialRoads:
w = (x2, y2)
dis[w] = min(dis[w], dv + abs(x1 - vx) + abs(y1 - vy) + cost)