题目（难度中等）
给你一个数组 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 <= 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
分析
首先本题的题意还是有点不清晰，“特殊路径”是有向路径，这一点题目和样例都没有强调。
称特殊路径的起点和终点为“特殊点”。从start 到 target 的路径肯定是：从 start 出发，经过若干个（可能为零个）特殊点，然后再走到 target。因此答案其实就是 start、target 和特殊点构成的有向图上，从 start 到 target 的最短路。我们只要根据题意构造出有向图，然后用 dijkstra 计算最短路即可。
设特殊路径有 m 条，则特殊点共有 2m 个。由于任意两点均可以到达，因此这张图是完全图，边数为O(m^2)。因此总体复杂度为 O(m^2 logm)。
代码
class Solution {public:int minimumCost(vector<int>& start, vector<int>& target, vector<vector<int>>& specialRoads) {typedef pair<int, int> pii;// mp 里存着某个坐标在有向图里的编号map<pii, int> mp;// 往图里添加一个坐标为 (x, y) 的点auto add = [&](int x, int y) {pii p = pii(x, y);if (mp.count(p)) return; // 重复点不存入int idx = mp.size(); // 点的编号mp[p] = idx;};// 把起点和终点添加到图里add(start[0], start[1]);add(target[0], target[1]);// 把特殊路径的端点添加到图里for (auto &road : specialRoads) add(road[0], road[1]), add(road[2], road[3]);int n = mp.size();// 记录一下每个点的横坐标和纵坐标，方便建图int X[n], Y[n];for (auto it = mp.begin(); it != mp.end(); it++) {X[it->second] = it->first.first;Y[it->second] = it->first.second;}// 开始构建有向图vector<int> e[n]; // 索引&值 组成记录边的数组vector<long long> v[n]; // 边的权值// 首先，任意两点之间都可以互相直接到达for (int i = 0; i < n; i++) // 起点for (int j = 0; j < n; j++) // 终点if (i != j){e[i].push_back(j); // 记录边v[i].push_back(abs(X[i] - X[j]) + abs(Y[i] - Y[j])); // 权值}// 其次，图里还存在特殊路径for (auto &road : specialRoads) {int sn = mp[pii(road[0], road[1])]; // 起点标号int fn = mp[pii(road[2], road[3])]; // 终点标号e[sn].push_back(fn);v[sn].push_back(road[4]); // 权值}// dijkstra 求从 S 到 T 的最短路int S = mp[pii(start[0], start[1])], T = mp[pii(target[0], target[1])];long long dis[n];memset(dis, -1, sizeof(dis));typedef pair<long long, int> pli;priority_queue<pli> pq;pq.push(pli(0, S));while (!pq.empty()) {pli p = pq.top(); pq.pop();int sn = p.second;long long d = -p.first;if(sn==T) return d;if (dis[sn] >= 0) continue;dis[sn] = d;for (int i = 0; i < e[sn].size(); i++) {int fn = e[sn][i];if (dis[fn] >= 0) continue;pq.push(pli(-d - v[sn][i], fn));}}return dis[T];}};
题目链接
https://leetcode.cn/problems/minimum-cost-of-a-path-with-special-roads
参考链接
https://leetcode.cn/problems/minimum-cost-of-a-path-with-special-roads/solution/jian-tu-zui-duan-lu-by-tsreaper-r094/
