#2327. 前往目标的最小代价

前往目标的最小代价

给你一个数组 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) 所需的 最小 代价。

格式

输入

第一行:起始位置 第二行:目标位置 第三行:特殊通道数量n 下面n行: specialRoads[i] = [x1i, y1i, x2i, y2i, costi]

输出

(startX, startY)(targetX, targetY) 所需的 最小 代价。

示例 1:

​输入:​

1 1
4 5
2
1 2 3 3 2
3 4 4 5 1

​输出:​5

解释:

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

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

示例 2:

​输入:​

3 2
5 7
4
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:

​输入:​

1 1
10 4
4
4 2 1 1 3
1 2 7 4 4
10 3 6 1 2
6 1 1 2 3

输出: 8

解释:

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

提示:

  • 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