Leetcode 2662. Minimum Cost of a Path With Special Roads

[Woodyiiiiiii]

2662. Minimum Cost of a Path With Special Roads

• 2662. Minimum Cost of a Path With Special Roads
• 无需建图，直接朴素 Dijkstra 求最短路（Python/Java/C++/Go）

类似题目：

• 1786. Number of Restricted Paths From First to Last Node

首先这道题我一开始想看成深度优先遍历来做，有些想歪了。

这实际上是个有向图求两点最短路径的问题，有一些特殊有向路径，那么这类问题可以用Dijkstra来做。

那么平时的Dijkstra都是在图结构上做的，用堆来模拟。但这里就比较难用堆的思路来写。那么我们回归本质，单纯用距离数组和访问数组来求解。

思路：把起点、终点和特殊路径终点看成图上的点，然后构造距离数组和访问数组，距离数组用Java里的Map<List,Integer>来表示，Key值用List是为了方便hash，单纯用int[]数组是不行的；访问数组的作用是每次遍历距离数组选出未访问的最小距离点，因为距离都是正值，其他点到该点的距离可以肯定是比这个最小值还大的，所以标记访问后下次就不用访问了。每次遍历中如果选不出最小值或者最小值仍未极限值，则说明已经结束返回-1，否则判断是否是终点起点；最后还要记得更新与终点的距离。

Tips: 距离数组表示的是起点到各个点的曼哈顿距离，所以有叠加性；因为曼哈顿距离固定，所以只能在特殊路径上缩短距离，所以记录特殊路径终点；因为是稠密图，所以，点比边少，所以用朴素Dijkstra。

时间复杂度：O(n^2)
空间复杂度：O(n)

class Solution {
    public int minimumCost(int[] start, int[] target, int[][] specialRoads) {
        if (start[0] == target[0] && start[1] == target[1]) {
            return 0;
        }
        Set<List<Integer>> v = new HashSet<>();
        Map<List<Integer>, Integer> dist = new HashMap<>();
        dist.put(Arrays.asList(start[0], start[1]), 0);
        dist.put(Arrays.asList(target[0], target[1]), Integer.MAX_VALUE);
        while (true) {
            List<Integer> cur = null;
            int min = Integer.MAX_VALUE;
            for (Map.Entry<List<Integer>, Integer> entry : dist.entrySet()) {
                if (v.contains(entry.getKey())) {
                    continue;
                }
                if (entry.getValue() < min) {
                    min = entry.getValue();
                    cur = entry.getKey();
                }
            }
            if (cur == null) {
                return -1;
            }
            if (cur.get(0) == target[0] && cur.get(1) == target[1]) {
                return min;
            }
            v.add(cur);
            // target
            dist.put(Arrays.asList(target[0], target[1]),
                    Math.min(dist.get(Arrays.asList(target[0], target[1])), min + Math.abs(cur.get(0) - target[0]) + Math.abs(cur.get(1) - target[1])));
            for (int[] road : specialRoads) {
                int nx = road[2], ny = road[3];
                if (v.contains(Arrays.asList(nx, ny))) {
                    continue;
                }
                int d = Math.min(Math.abs(cur.get(0) - nx) + Math.abs(cur.get(1) - ny),
                        road[4] + Math.abs(cur.get(0) - road[0]) + Math.abs(cur.get(1) - road[1])) + min;
                dist.put(Arrays.asList(nx, ny), Math.min(dist.getOrDefault(Arrays.asList(nx, ny), Integer.MAX_VALUE), d));
            }
        }
    }
}