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 == 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

# 建图 + Dijkstra 算法

	class Solution {
	public int minimumCost(int[] start, int[] target, int[][] specialRoads) {
	int n = specialRoads.length;
	// 构图
	Map<Pair, Set<Pair>> map = new HashMap<>();
	for (int[] specialRoad : specialRoads) {
	Pair pair = new Pair(specialRoad[0], specialRoad[1], specialRoad[4]);
	Pair pair1 = new Pair(specialRoad[2], specialRoad[3], specialRoad[4]);
	Set<Pair> pairs = map.computeIfAbsent(pair, o -> new HashSet<>());
	map.computeIfAbsent(pair1, o -> new HashSet<>());
	// 选择最小的，有可能特殊路径大于本身的距离
	pair1.w = Math.min(pair1.w, Math.abs(pair.x - pair1.x) + Math.abs(pair.y - pair1.y));
	pairs.add(pair1);
	}
	Set<Pair> pairs1 = new HashSet<>(map.keySet());
	for (Pair pair : pairs1) {
	Set<Pair> pairs = map.get(pair);
	Pair s = new Pair(start[0], start[1], Math.abs(start[0] - pair.x) + Math.abs(start[1] - pair.y));
	if (!pairs.contains(s)) {
	pairs.add(s);
	}
	Set<Pair> sp = map.computeIfAbsent(s, o -> new HashSet<>());
	if (!sp.contains(pair)) {
	sp.add(new Pair(pair.x, pair.y, Math.abs(start[0] - pair.x) + Math.abs(start[1] - pair.y)));
	}
	Pair t = new Pair(target[0], target[1], Math.abs(target[0] - pair.x) + Math.abs(target[1] - pair.y));
	Set<Pair> tp = map.computeIfAbsent(t, o -> new HashSet<>());
	if (!tp.contains(pair)) {
	tp.add(new Pair(pair.x, pair.y, Math.abs(target[0] - pair.x) + Math.abs(target[1] - pair.y)));
	}
	if (!pairs.contains(t)) {
	pairs.add(t);
	}
	for (int[] specialRoad : specialRoads) {
	if (pair.x != specialRoad[0] \|\| pair.y != specialRoad[1]) {
	pairs.add(new Pair(specialRoad[2], specialRoad[3], Math.abs(specialRoad[2] - pair.x) + Math.abs(specialRoad[3] - pair.y)));
	pairs.add(new Pair(specialRoad[0], specialRoad[1], Math.abs(specialRoad[0] - pair.x) + Math.abs(specialRoad[1] - pair.y)));
	}
	}
	}
	PriorityQueue<Pair> minHeap = new PriorityQueue<>((o1, o2) -> o1.w - o2.w);
	minHeap.add(new Pair(start[0], start[1], 0));
	Map<Pair, Integer> dis = new HashMap<>();
	for (Pair pair : map.keySet()) {
	dis.put(pair, Integer.MAX_VALUE / 2);
	}
	dis.put(new Pair(start[0], start[1], 0), 0);
	while (!minHeap.isEmpty()) {
	Pair u = minHeap.poll();
	if (u.x == target[0] && u.y == target[1]) {
	return dis.get(u);
	}
	int w = dis.get(u);
	Set<Pair> pairs = map.get(u);
	for (Pair pair : pairs) {
	int next = w + pair.w;
	if (next >= dis.get(pair)) {
	continue;
	}
	pair.w = next;
	dis.put(pair, next);
	minHeap.add(pair);
	}
	}
	return -1;
	}
	}

	class Pair {
	int x;
	int y;
	int w;

	public Pair(int x, int y, int w) {
	this.x = x;
	this.y = y;
	this.w = w;
	}

	@Override
	public boolean equals(Object o) {
	if (this == o) return true;
	if (o == null \|\| getClass() != o.getClass()) return false;
	Pair pair = (Pair) o;
	return x == pair.x && y == pair.y;
	}

	@Override
	public int hashCode() {
	return Objects.hash(x, y);
	}
	}

# 复杂度分析

时间复杂度： $O(mlog(n))$ ，其中 $m$ 为边数，由于这是稠密图，有 $m=n^2$
空间复杂度： $O(n)$

# 朴素 Dijkstra 算法

定义 $dis[i]$ 表示从 $start$ 到 $i$ 的最短路的距离

首先，从 $start$ 出发，更新邻居的最短路。

从 $start$ 到达 $target$ 的曼哈顿距离
从 $start$ 到达特殊路径的终点的曼哈顿距离；与从 $start$ 到达特殊路径的起点的曼哈顿距离，再从特殊路径的起点到达特殊路径终点的代价距离。二者及自身取较小者
为什么只需要看从 $start$ 到达特殊路径终点的距离即可，而不需要考虑从 $start$ 到达特殊路径起点？

如下图所示：

(1, 1) -> (4, 5) 的曼哈顿距离必然大于 (1, 1) -> (1, 2) -> (4,5) 的曼哈顿路径
- 由三角不等式可以得出
所以无需考虑从 $start$ ： (1, 1) 到达特殊路径： (1, 2) 起点。

更无需考虑从 (1, 1) -> (1, 2) -> (3, 4) -> ... 的曼哈顿距离
- 因为 (1, 1) -> ... 的曼哈顿距离必然小于前者
但是若由代价距离则需要考虑，如下图所示：

(1, 1) -> (1, 2) -> (3, 3) 路径中， (1, 2) -> (3, 3) 不再是曼哈顿距离，而是二者的代价距离，代价距离有可能小于二者的曼哈顿距离，所以需要判断从 $start$ 到达特殊路径的起点的曼哈顿距离，再从特殊路径的起点到达特殊路径终点的代价距离。
- $start$ ： (1, 1)
- 特殊路径起点： (1, 2)
- 特殊路径终点： (3, 3)

	class Solution {
	public int minimumCost(int[] start, int[] target, int[][] specialRoads) {
	Pair t = new Pair(target[0], target[1]);
	//start 到达 i 的最短距离 dis
	Map<Pair, Integer> dis = new HashMap<>();
	// 去重
	Set<Pair> vis = new HashSet<>();
	dis.put(new Pair(start[0], start[1]), 0);

	while (true) {
	Pair pair = null;
	int d = Integer.MAX_VALUE;
	// 寻找最短距离
	for (Pair v : dis.keySet()) {
	if (!vis.contains(v) && dis.get(v) < d) {
	d = dis.get(v);
	pair = v;
	}
	}
	vis.add(pair);
	// 是终点
	if (pair.equals(t)) {
	return d;
	}
	// 更新到达终点的最短路径 (x, y) -> (tx, ty), 曼哈顿距离
	dis.put(t, Math.min(dis.getOrDefault(t, Integer.MAX_VALUE),
	d + Math.abs(t.x - pair.x) + Math.abs(t.y - pair.y)));
	// 更新到达特殊路径终点的最短路径 (x, y) -> (xs, ys) -> (xe, ye), (xs, ys) -> (xe, ye) 为代价距离
	for (int[] specialRoad : specialRoads) {
	int xs = specialRoad[0], ys = specialRoad[1], xe = specialRoad[2], ye = specialRoad[3];
	Pair pe = new Pair(xe, ye);
	if (vis.contains(pe)) {
	continue;
	}
	int nDis = d +
	//(x, y) -> (xs, ys) 的曼哈顿
	Math.abs(xs - pair.x) + Math.abs(ys - pair.y) +
	//(xs, ys) -> (xe, ye) 的代价距离
	specialRoad[4];

	dis.put(pe, Math.min(dis.getOrDefault(pe, Integer.MAX_VALUE),
	Math.min(nDis,
	//(x, y) -> (xe, ye) 的曼哈顿
	d + Math.abs(xe - pair.x) + Math.abs(ye - pair.y))));
	}
	}
	}
	}

	class Pair {
	int x;
	int y;

	public Pair(int x, int y) {
	this.x = x;
	this.y = y;
	}

	@Override
	public boolean equals(Object o) {
	if (this == o) return true;
	if (o == null \|\| getClass() != o.getClass()) return false;
	Pair pair = (Pair) o;
	return x == pair.x && y == pair.y;
	}

	@Override
	public int hashCode() {
	return Objects.hash(x, y);
	}
	}

# 复杂度分析

时间复杂度： $O(n^2)$ ，其中 $n$ 为 $specialRoads$ 的长度
空间复杂度： $O(n)$

中等最短路图数组

# 建图 + Dijkstra 算法

# 复杂度分析

# 朴素 Dijkstra 算法

# 复杂度分析

数位 dp 模板 至少有 1 位重复的数字

推箱子

数位 dp 模板至少有 1 位重复的数字