建图，从 $\textit{original}[i]$ 向 $\textit{changed}[i]$ 连边，边权为 $\textit{cost}[i]$。

然后用 Floyd 算法求图中任意两点最短路，得到 $\textit{dis}$ 矩阵，原理请看 带你发明 Floyd 算法！包含为什么循环顺序是 $kij$ 的讲解。

这里得到的 $\textit{dis}[i][j]$ 表示字母 $i$ 通过若干次替换操作变成字母 $j$ 的最小成本。

最后累加所有 $\textit{dis}[\textit{original}[i]][\textit{changed}[i]]$，即为答案。如果答案为无穷大，返回 $-1$。

本题视频讲解

###py

class Solution:
    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
        dis = [[inf] * 26 for _ in range(26)]
        for i in range(26):
            dis[i][i] = 0

        for x, y, c in zip(original, changed, cost):
            x = ord(x) - ord('a')
            y = ord(y) - ord('a')
            dis[x][y] = min(dis[x][y], c)

        for k in range(26):
            for i in range(26):
                if dis[i][k] == inf:
                    continue  # 巨大优化！
                for j in range(26):
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])

        ans = sum(dis[ord(x) - ord('a')][ord(y) - ord('a')] for x, y in zip(source, target))
        return ans if ans < inf else -1

###java

class Solution {
    public long minimumCost(String source, String target, char[] original, char[] changed, int[] cost) {
        final int INF = Integer.MAX_VALUE / 2;
        int[][] dis = new int[26][26];
        for (int i = 0; i < 26; i++) {
            Arrays.fill(dis[i], INF);
            dis[i][i] = 0;
        }
        for (int i = 0; i < cost.length; i++) {
            int x = original[i] - 'a';
            int y = changed[i] - 'a';
            dis[x][y] = Math.min(dis[x][y], cost[i]);
        }
        for (int k = 0; k < 26; k++) {
            for (int i = 0; i < 26; i++) {
                if (dis[i][k] == INF) {
                    continue; // 巨大优化！
                }
                for (int j = 0; j < 26; j++) {
                    dis[i][j] = Math.min(dis[i][j], dis[i][k] + dis[k][j]);
                }
            }
        }

        long ans = 0;
        for (int i = 0; i < source.length(); i++) {
            int d = dis[source.charAt(i) - 'a'][target.charAt(i) - 'a'];
            if (d == INF) {
                return -1;
            }
            ans += d;
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    long long minimumCost(string source, string target, vector<char>& original, vector<char>& changed, vector<int>& cost) {
        const int INF = 0x3f3f3f3f;
        int dis[26][26];
        memset(dis, 0x3f, sizeof(dis));
        for (int i = 0; i < 26; i++) {
            dis[i][i] = 0;
        }
        for (int i = 0; i < cost.size(); i++) {
            int x = original[i] - 'a';
            int y = changed[i] - 'a';
            dis[x][y] = min(dis[x][y], cost[i]);
        }
        for (int k = 0; k < 26; k++) {
            for (int i = 0; i < 26; i++) {
                if (dis[i][k] == INF) {
                    continue; // 巨大优化！
                }
                for (int j = 0; j < 26; j++) {
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
                }
            }
        }

        long long ans = 0;
        for (int i = 0; i < source.length(); i++) {
            int d = dis[source[i] - 'a'][target[i] - 'a'];
            if (d == INF) {
                return -1;
            }
            ans += d;
        }
        return ans;
    }
};

###go

func minimumCost(source, target string, original, changed []byte, cost []int) (ans int64) {
const inf = math.MaxInt / 2
dis := [26][26]int{}
for i := range dis {
for j := range dis[i] {
if j != i {
dis[i][j] = inf
}
}
}
for i, c := range cost {
x := original[i] - 'a'
y := changed[i] - 'a'
dis[x][y] = min(dis[x][y], c)
}
for k := range dis {
for i := range dis {
if dis[i][k] == inf {
continue // 巨大优化！
}
for j := range dis {
dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j])
}
}
}

for i, b := range source {
d := dis[b-'a'][target[i]-'a']
if d == inf {
return -1
}
ans += int64(d)
}
return
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n+m+|\Sigma|^3)$，其中 $n$ 为 $\textit{source}$ 的长度，$m$ 为 $\textit{cost}$ 的长度，$|\Sigma|$ 为字符集合的大小，本题中字符均为小写字母，所以 $|\Sigma|=26$。
• 空间复杂度：$\mathcal{O}(|\Sigma|^2)$。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
7. 动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

如果没有传送，本题就是 64. 最小路径和。注意本题不计入起点的值。

接着 64 题我的题解 继续讲。

在有传送的情况下，可以用一个额外的维度表示传送次数。定义 $f[t][i+1][j+1]$ 表示在使用恰好 $t$ 次传送的情况下，从左上角 $(0,0)$ 到 $(i,j)$ 的最小总成本。

考虑转移来源，即我们是从哪个格子移动到 $(i,j)$ 的。

• 普通移动：从 $(i,j-1)$ 和 $(i-1,j)$ 移动到 $(i,j)$。转移来源分别为 $f[t][i+1][j]$ 和 $f[t][i][j+1]$。
• 传送：设 $x = \textit{grid}[i][j]$，我们可以从格子值 $\ge x$ 的任意格子传送到 $(i,j)$。转移来源为 $f[t-1][i'+1][j'+1]$，满足 $\textit{grid}[i'][j']\ge x$。如何快速得到这些 $f[t-1][i'+1][j'+1]$ 的最小值？
  • 定义 $\textit{sufMinF}_{t-1}[x]$ 表示满足 $\textit{grid}[i][j]\ge x$ 的 $f[t-1][i+1][j+1]$ 的最小值。
  • 在计算完 $f[t-1][i+1][j+1]$ 后，把格子值 $x=\textit{grid}[i][j]$ 及其对应的状态值 $f[t-1][i+1][j+1]$ 保存到一个数组 $\textit{minF}$ 中，其中 $\textit{minF}[x]$ 表示格子值为 $x$ 的最小状态值（如果不存在则为 $\infty$）。然后倒序遍历 $\textit{minF}$，计算后缀最小值，即为 $\textit{sufMinF}_{t-1}$。

状态转移方程为

$$
f[t][i+1][j+1] = \min(f[t][i+1][j] + x, f[t][i][j+1] + x, \textit{sufMinF}_{t-1}[x])
$$

其中 $x = \textit{grid}[i][j]$。

初始值同 64 题。

答案为 $f[k][m-1][n-1]$。虽然题目要求使用「至多」$k$ 次传送，但由于我们可以原地传送，所以传送的次数越多，总成本是不会增大的。所以「至多」$k$ 次传送等于「恰好」$k$ 次传送。

代码实现时，$f$ 数组的前两个维度可以优化掉。

具体请看 视频讲解，欢迎点赞关注~

###py

# 手写 min 更快
min = lambda a, b: b if b < a else a

class Solution:
    def minCost(self, grid: List[List[int]], k: int) -> int:
        n = len(grid[0])
        mx = max(map(max, grid))

        suf_min_f = [inf] * (mx + 2)
        for _ in range(k + 1):
            min_f = [inf] * (mx + 1)

            # 64. 最小路径和（空间优化写法）
            f = [inf] * (n + 1)
            f[1] = -grid[0][0]  # 起点的成本不算
            for row in grid:
                for j, x in enumerate(row):
                    f[j + 1] = min(min(f[j], f[j + 1]) + x, suf_min_f[x])
                    min_f[x] = min(min_f[x], f[j + 1])
   
            # 计算 min_f 的后缀最小值
            for i in range(mx, -1, -1):
                suf_min_f[i] = min(suf_min_f[i + 1], min_f[i])

        return f[n]

###java

class Solution {
    public int minCost(int[][] grid, int k) {
        int n = grid[0].length;
        int mx = 0;
        for (int[] row : grid) {
            for (int x : row) {
                mx = Math.max(mx, x);
            }
        }

        int[] sufMinF = new int[mx + 2];
        Arrays.fill(sufMinF, Integer.MAX_VALUE);
        int[] minF = new int[mx + 1];
        int[] f = new int[n + 1];

        for (int t = 0; t <= k; t++) {
            Arrays.fill(minF, Integer.MAX_VALUE);

            // 64. 最小路径和（空间优化写法）
            Arrays.fill(f, Integer.MAX_VALUE / 2);
            f[1] = -grid[0][0]; // 起点的成本不算
            for (int[] row : grid) {
                for (int j = 0; j < n; j++) {
                    int x = row[j];
                    f[j + 1] = Math.min(Math.min(f[j], f[j + 1]) + x, sufMinF[x]);
                    minF[x] = Math.min(minF[x], f[j + 1]);
                }
            }

            // 计算 minF 的后缀最小值
            for (int i = mx; i >= 0; i--) {
                sufMinF[i] = Math.min(sufMinF[i + 1], minF[i]);
            }
        }

        return f[n];
    }
}

###cpp

class Solution {
public:
    int minCost(vector<vector<int>>& grid, int k) {
        int n = grid[0].size();
        int mx = 0;
        for (auto& row : grid) {
            mx = max(mx, ranges::max(row));
        }

        vector<int> suf_min_f(mx + 2, INT_MAX);
        vector<int> min_f(mx + 1);
        vector<int> f(n + 1);

        for (int t = 0; t <= k; t++) {
            ranges::fill(min_f, INT_MAX);

            // 64. 最小路径和（空间优化写法）
            ranges::fill(f, INT_MAX / 2);
            f[1] = -grid[0][0]; // 起点的成本不算
            for (auto& row : grid) {
                for (int j = 0; j < n; j++) {
                    int x = row[j];
                    f[j + 1] = min(min(f[j], f[j + 1]) + x, suf_min_f[x]);
                    min_f[x] = min(min_f[x], f[j + 1]);
                }
            }

            // 计算 min_f 的后缀最小值
            for (int i = mx; i >= 0; i--) {
                suf_min_f[i] = min(suf_min_f[i + 1], min_f[i]);
            }
        }

        return f[n];
    }
};

###go

func minCost(grid [][]int, k int) int {
n := len(grid[0])
mx := 0
for _, row := range grid {
mx = max(mx, slices.Max(row))
}

sufMinF := make([]int, mx+2)
for i := range sufMinF {
sufMinF[i] = math.MaxInt
}
minF := make([]int, mx+1)
f := make([]int, n+1)

for range k + 1 {
for i := range minF {
minF[i] = math.MaxInt
}

// 64. 最小路径和（空间优化写法）
for i := range f {
f[i] = math.MaxInt / 2
}
f[1] = -grid[0][0] // 起点的成本不算
for _, row := range grid {
for j, x := range row {
f[j+1] = min(f[j]+x, f[j+1]+x, sufMinF[x])
minF[x] = min(minF[x], f[j+1])
}
}

// 计算 minF 的后缀最小值
for i := mx; i >= 0; i-- {
sufMinF[i] = min(sufMinF[i+1], minF[i])
}
}

return f[n]
}

优化

每次循环我们会计算一遍 $\textit{sufMinF}$。如果发现某次循环没有改变 $\textit{sufMinF}$，那么无论再传送多少次，都不会再改变 $\textit{sufMinF}$ 了，此时我们已经找到了答案。

力扣喜欢出随机数据。测试发现，对于 $m=n=80$，值域在 $[0,10^4]$ 中随机的测试数据，平均迭代约 $2.2$ 次就收敛了，然后再循环一次发现收敛，即 $\textit{sufMinF}$ 在循环前后是相同的。所以平均外层循环约 $3.2$ 次就可以退出循环了，而不是循环 $k+1$ 次。

此外，如果 $k>0$ 且可以直接跳到终点，即 $\textit{grid}[0][0]\ge \textit{grid}[m-1][n-1]$，那么直接返回 $0$。

###py

# 手写 min 更快
min = lambda a, b: b if b < a else a

class Solution:
    def minCost(self, grid: List[List[int]], k: int) -> int:
        if k and grid[0][0] >= grid[-1][-1]:
            return 0

        n = len(grid[0])
        mx = max(map(max, grid))

        suf_min_f = [inf] * (mx + 2)
        for _ in range(k + 1):
            min_f = [inf] * (mx + 1)

            # 64. 最小路径和（空间优化写法）
            f = [inf] * (n + 1)
            f[1] = -grid[0][0]  # 起点的成本不算
            for row in grid:
                for j, x in enumerate(row):
                    f[j + 1] = min(min(f[j], f[j + 1]) + x, suf_min_f[x])
                    min_f[x] = min(min_f[x], f[j + 1])
   
            tmp = suf_min_f.copy()
            # 计算 min_f 的后缀最小值
            for i in range(mx, -1, -1):
                suf_min_f[i] = min(suf_min_f[i + 1], min_f[i])
            if suf_min_f == tmp:
                # 收敛了：传送不改变 suf_min_f，那么无论再传送多少次都不会改变 suf_min_f
                break

        return f[n]

###java

class Solution {
    public int minCost(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        if (k > 0 && grid[0][0] >= grid[m - 1][n - 1]) {
            return 0;
        }

        int mx = 0;
        for (int[] row : grid) {
            for (int x : row) {
                mx = Math.max(mx, x);
            }
        }

        int[] sufMinF = new int[mx + 2];
        Arrays.fill(sufMinF, Integer.MAX_VALUE);
        int[] minF = new int[mx + 1];
        int[] f = new int[n + 1];

        for (int t = 0; t <= k; t++) {
            Arrays.fill(minF, Integer.MAX_VALUE);

            // 64. 最小路径和（空间优化写法）
            Arrays.fill(f, Integer.MAX_VALUE / 2);
            f[1] = -grid[0][0]; // 起点的成本不算
            for (int[] row : grid) {
                for (int j = 0; j < n; j++) {
                    int x = row[j];
                    f[j + 1] = Math.min(Math.min(f[j], f[j + 1]) + x, sufMinF[x]);
                    minF[x] = Math.min(minF[x], f[j + 1]);
                }
            }

            boolean done = true;
            // 计算 minF 的后缀最小值
            for (int i = mx; i >= 0; i--) {
                int mn = Math.min(sufMinF[i + 1], minF[i]);
                if (mn < sufMinF[i]) {
                    sufMinF[i] = mn;
                    done = false;
                }
            }
            if (done) {
                // 收敛了：传送不改变 sufMinF，那么无论再传送多少次都不会改变 sufMinF
                break;
            }
        }

        return f[n];
    }
}

###cpp

class Solution {
public:
    int minCost(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        if (k && grid[0][0] >= grid[m - 1][n - 1]) {
            return 0;
        }

        int mx = 0;
        for (auto& row : grid) {
            mx = max(mx, ranges::max(row));
        }

        vector<int> suf_min_f(mx + 2, INT_MAX);
        vector<int> min_f(mx + 1);
        vector<int> f(n + 1);

        for (int t = 0; t <= k; t++) {
            ranges::fill(min_f, INT_MAX);

            // 64. 最小路径和（空间优化写法）
            ranges::fill(f, INT_MAX / 2);
            f[1] = -grid[0][0]; // 起点的成本不算
            for (auto& row : grid) {
                for (int j = 0; j < n; j++) {
                    int x = row[j];
                    f[j + 1] = min(min(f[j], f[j + 1]) + x, suf_min_f[x]);
                    min_f[x] = min(min_f[x], f[j + 1]);
                }
            }

            auto tmp = suf_min_f;
            // 计算 min_f 的后缀最小值
            for (int i = mx; i >= 0; i--) {
                suf_min_f[i] = min(suf_min_f[i + 1], min_f[i]);
            }
            if (suf_min_f == tmp) {
                // 收敛了：传送不改变 suf_min_f，那么无论再传送多少次都不会改变 suf_min_f
                break;
            }
        }

        return f[n];
    }
};

###go

func minCost(grid [][]int, k int) int {
m, n := len(grid), len(grid[0])
if k > 0 && grid[0][0] > grid[m-1][n-1] {
return 0
}

mx := 0
for _, row := range grid {
mx = max(mx, slices.Max(row))
}

sufMinF := make([]int, mx+2)
for i := range sufMinF {
sufMinF[i] = math.MaxInt
}
minF := make([]int, mx+1)
f := make([]int, n+1)

for range k + 1 {
for i := range minF {
minF[i] = math.MaxInt
}

// 64. 最小路径和（空间优化写法）
for i := range f {
f[i] = math.MaxInt / 2
}
f[1] = -grid[0][0] // 起点的成本不算
for _, row := range grid {
for j, x := range row {
f[j+1] = min(f[j]+x, f[j+1]+x, sufMinF[x])
minF[x] = min(minF[x], f[j+1])
}
}

done := true
// 计算 minF 的后缀最小值
for i := mx; i >= 0; i-- {
mn := min(sufMinF[i+1], minF[i])
if mn < sufMinF[i] {
sufMinF[i] = mn
done = false
}
}
if done {
// 收敛了：传送不改变 sufMinF，那么无论再传送多少次都不会改变 sufMinF
break
}
}
return f[n]
}

复杂度分析

• 时间复杂度：$\mathcal{O}((mn+U)k)$，其中 $m$ 和 $n$ 分别为 $\textit{grid}$ 的行数和列数，$U$ 为 $\textit{grid}[i][j]$ 的最大值。
• 空间复杂度：$\mathcal{O}(n+U)$。

专题训练

见下面动态规划题单的「二、网格图 DP」和「§7.6 多维 DP」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

Dijkstra 算法介绍

根据 Dijkstra 算法，同一个节点我们只会访问一次，所以「最多可使用一次开关」这个约束是多余的，我们只需把反向边的边权设置为 $2w_i$ 即可。答案为 $0$ 到 $n-1$ 的最短路长度。

###py

class Solution:
    def minCost(self, n: int, edges: List[List[int]]) -> int:
        g = [[] for _ in range(n)]  # 邻接表
        for x, y, wt in edges:
            g[x].append((y, wt))
            g[y].append((x, wt * 2))

        dis = [inf] * n
        dis[0] = 0  # 起点到自己的距离是 0
        h = [(0, 0)]  # 堆中保存 (起点到节点 x 的最短路长度，节点 x)

        while h:
            dis_x, x = heappop(h)
            if dis_x > dis[x]:  # x 之前出堆过
                continue
            if x == n - 1:  # 到达终点
                return dis_x
            for y, wt in g[x]:
                new_dis_y = dis_x + wt
                if new_dis_y < dis[y]:
                    dis[y] = new_dis_y  # 更新 x 的邻居的最短路
                    # 懒更新堆：只插入数据，不更新堆中数据
                    # 相同节点可能有多个不同的 new_dis_y，除了最小的 new_dis_y，其余值都会触发上面的 continue
                    heappush(h, (new_dis_y, y))

        return -1

###java

class Solution {
    public int minCost(int n, int[][] edges) {
        List<int[]>[] g = new ArrayList[n]; // 邻接表
        Arrays.setAll(g, _ -> new ArrayList<>());
        for (int[] e : edges) {
            int x = e[0];
            int y = e[1];
            int wt = e[2];
            g[x].add(new int[]{y, wt});
            g[y].add(new int[]{x, wt * 2});
        }

        int[] dis = new int[n];
        Arrays.fill(dis, Integer.MAX_VALUE);
        // 堆中保存 (起点到节点 x 的最短路长度，节点 x)
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        dis[0] = 0; // 起点到自己的距离是 0
        pq.offer(new int[]{0, 0});

        while (!pq.isEmpty()) {
            int[] p = pq.poll();
            int disX = p[0];
            int x = p[1];
            if (disX > dis[x]) { // x 之前出堆过
                continue;
            }
            if (x == n - 1) { // 到达终点
                return disX;
            }
            for (int[] e : g[x]) {
                int y = e[0];
                int wt = e[1];
                int newDisY = disX + wt;
                if (newDisY < dis[y]) {
                    dis[y] = newDisY; // 更新 x 的邻居的最短路
                    // 懒更新堆：只插入数据，不更新堆中数据
                    // 相同节点可能有多个不同的 newDisY，除了最小的 newDisY，其余值都会触发上面的 continue
                    pq.offer(new int[]{newDisY, y});
                }
            }
        }

        return -1;
    }
}

###cpp

class Solution {
public:
    int minCost(int n, vector<vector<int>>& edges) {
        vector<vector<pair<int, int>>> g(n); // 邻接表
        for (auto& e : edges) {
            int x = e[0], y = e[1], wt = e[2];
            g[x].emplace_back(y, wt);
            g[y].emplace_back(x, wt * 2);
        }

        vector<int> dis(n, INT_MAX);
        // 堆中保存 (起点到节点 x 的最短路长度，节点 x)
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
        dis[0] = 0; // 起点到自己的距离是 0
        pq.emplace(0, 0);

        while (!pq.empty()) {
            auto [dis_x, x] = pq.top();
            pq.pop();
            if (dis_x > dis[x]) { // x 之前出堆过
                continue;
            }
            if (x == n - 1) { // 到达终点
                return dis_x;
            }
            for (auto& [y, wt] : g[x]) {
                auto new_dis_y = dis_x + wt;
                if (new_dis_y < dis[y]) {
                    dis[y] = new_dis_y; // 更新 x 的邻居的最短路
                    // 懒更新堆：只插入数据，不更新堆中数据
                    // 相同节点可能有多个不同的 new_dis_y，除了最小的 new_dis_y，其余值都会触发上面的 continue
                    pq.emplace(new_dis_y, y);
                }
            }
        }

        return -1;
    }
};

###go

func minCost(n int, edges [][]int) int {
type edge struct{ to, wt int }
g := make([][]edge, n) // 邻接表
for _, e := range edges {
x, y, wt := e[0], e[1], e[2]
g[x] = append(g[x], edge{y, wt})
g[y] = append(g[y], edge{x, wt * 2}) // 反转边
}

dis := make([]int, n)
for i := range dis {
dis[i] = math.MaxInt
}
dis[0] = 0 // 起点到自己的距离是 0
// 堆中保存 (起点到节点 x 的最短路长度，节点 x)
h := &hp{{}}

for h.Len() > 0 {
p := heap.Pop(h).(pair)
disX, x := p.dis, p.x
if disX > dis[x] { // x 之前出堆过
continue
}
if x == n-1 { // 到达终点
return disX
}
for _, e := range g[x] {
y := e.to
newDisY := disX + e.wt
if newDisY < dis[y] {
dis[y] = newDisY // 更新 x 的邻居的最短路
// 懒更新堆：只插入数据，不更新堆中数据
// 相同节点可能有多个不同的 newDisY，除了最小的 newDisY，其余值都会触发上面的 continue
heap.Push(h, pair{newDisY, y})
}
}
}

return -1
}

type pair struct{ dis, x int }
type hp []pair

func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].dis < h[j].dis }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any)        { *h = append(*h, v.(pair)) }
func (h *hp) Pop() (v any)      { a := *h; *h, v = a[:len(a)-1], a[len(a)-1]; return }

复杂度分析

• 时间复杂度：$\mathcal{O}(n+m\log m)$，其中 $m$ 是 $\textit{edges}$ 的长度。
• 空间复杂度：$\mathcal{O}(n+m)$。

专题训练

见下面图论题单的「§3.1 单源最短路：Dijkstra 算法」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

把 $\textit{arr}$ 排序后，最小绝对差只能来自相邻元素（不相邻的元素之差更大）。

遍历 $\textit{arr}$ 中的相邻元素 $(x,y)$，设绝对差为 $\textit{diff}=y-x$，当前最小绝对差为 $\textit{minDiff}$。

• 如果 $\textit{diff} < \textit{minDiff}$，那么更新 $\textit{minDiff}$ 为 $\textit{diff}$，更新答案为 $[[x,y]]$。
• 如果 $\textit{diff} = \textit{minDiff}$，那么把 $[x,y]$ 添加到答案中。

class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        arr.sort()
        min_diff = inf
        ans = []
        for x, y in pairwise(arr):
            diff = y - x
            if diff < min_diff:
                min_diff = diff
                ans = [[x, y]]
            elif diff == min_diff:
                ans.append([x, y])
        return ans

class Solution {
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        Arrays.sort(arr);
        int minDiff = Integer.MAX_VALUE;
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 1; i < arr.length; i++) {
            int x = arr[i - 1];
            int y = arr[i];
            int diff = y - x;
            if (diff < minDiff) {
                minDiff = diff;
                ans.clear();
                ans.add(List.of(x, y));
            } else if (diff == minDiff) {
                ans.add(List.of(x, y));
            }
        }
        return ans;
    }
}

class Solution {
public:
    vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
        ranges::sort(arr);
        int min_diff = INT_MAX;
        vector<vector<int>> ans;
        for (int i = 1; i < arr.size(); i++) {
            int x = arr[i - 1], y = arr[i];
            int diff = y - x;
            if (diff < min_diff) {
                min_diff = diff;
                ans = {{x, y}};
            } else if (diff == min_diff) {
                ans.push_back({x, y});
            }
        }
        return ans;
    }
};

int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int** minimumAbsDifference(int* arr, int arrSize, int* returnSize, int** returnColumnSizes) {
    qsort(arr, arrSize, sizeof(int), cmp);

    int min_diff = INT_MAX;
    int** ans = malloc((arrSize - 1) * sizeof(int*));
    int k = 0;

    for (int i = 0; i + 1 < arrSize; i++) {
        int x = arr[i];
        int y = arr[i + 1];
        int diff = y - x;
        if (diff < min_diff) {
            min_diff = diff;
            k = 0;
        }
        if (diff <= min_diff) {
            ans[k] = malloc(2 * sizeof(int));
            ans[k][0] = x;
            ans[k][1] = y;
            k++;
        }
    }

    *returnSize = k;
    *returnColumnSizes = malloc(k * sizeof(int));
    for (int i = 0; i < k; i++) {
        (*returnColumnSizes)[i] = 2;
    }
    return ans;
}

func minimumAbsDifference(arr []int) (ans [][]int) {
slices.Sort(arr)
minDiff := math.MaxInt
for i, x := range arr[:len(arr)-1] {
y := arr[i+1]
diff := y - x
if diff < minDiff {
minDiff = diff
ans = [][]int{{x, y}}
} else if diff == minDiff {
ans = append(ans, []int{x, y})
}
}
return
}

var minimumAbsDifference = function(arr) {
    arr.sort((a, b) => a - b);
    const ans = [];
    let minDiff = Infinity;
    for (let i = 1; i < arr.length; i++) {
        const x = arr[i - 1], y = arr[i];
        const diff = y - x;
        if (diff < minDiff) {
            minDiff = diff;
            ans.length = 0;
            ans.push([x, y]);
        } else if (diff === minDiff) {
            ans.push([x, y]);
        }
    }
    return ans;
};

impl Solution {
    pub fn minimum_abs_difference(mut arr: Vec<i32>) -> Vec<Vec<i32>> {
        arr.sort_unstable();
        let mut min_diff = i32::MAX;
        let mut ans = vec![];
        for i in 1..arr.len() {
            let x = arr[i - 1];
            let y = arr[i];
            let diff = y - x;
            if diff < min_diff {
                min_diff = diff;
                ans.clear();
                ans.push(vec![x, y]);
            } else if diff == min_diff {
                ans.push(vec![x, y]);
            }
        }
        ans
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n\log n)$，其中 $n$ 是 $\textit{arr}$ 的长度。瓶颈在排序上。
• 空间复杂度：$\mathcal{O}(1)$。返回值和排序的栈开销不计入。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

为方便计算差值，先把 $\textit{nums}$ 从小到大排序。

把 $\textit{nums}$ 中的元素画在一维数轴上。如果 $\textit{nums}[i]$ 是 $k$ 个数中的最大值，那么最小值的下标至多为 $i-k+1$（要在最小值和最大值之间再选 $k-2$ 个数）。但最小值越小，差值越大，所以最小值的下标恰好为 $i-k+1$ 是最优的。

枚举最大值的下标 $i = k-1,k,k+1,\ldots, n-1$，计算差值 $\textit{nums}[i] - \textit{nums}[i-k+1]$ 的最大值，即为答案。

class Solution:
def minimumDifference(self, nums: List[int], k: int) -> int:
nums.sort()
n = len(nums)
return min(nums[i] - nums[i - k + 1] for i in range(k - 1, n))

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        nums.sort()
        return min(mx - mn for mx, mn in zip(nums[k - 1:], nums))

class Solution {
public int minimumDifference(int[] nums, int k) {
Arrays.sort(nums);
int ans = Integer.MAX_VALUE;
for (int i = k - 1; i < nums.length; i++) {
ans = Math.min(ans, nums[i] - nums[i - k + 1]);
}
return ans;
}
}

class Solution {
public:
int minimumDifference(vector<int>& nums, int k) {
ranges::sort(nums);
int ans = INT_MAX;
for (int i = k - 1; i < nums.size(); i++) {
ans = min(ans, nums[i] - nums[i - k + 1]);
}
return ans;
}
};

#define MIN(a, b) ((b) < (a) ? (b) : (a))

int cmp(const void* a, const void* b) {
return *(int*)a - *(int*)b;
}

int minimumDifference(int* nums, int numsSize, int k) {
qsort(nums, numsSize, sizeof(int), cmp);
int ans = INT_MAX;
for (int i = k - 1; i < numsSize; i++) {
ans = MIN(ans, nums[i] - nums[i - k + 1]);
}
return ans;
}

func minimumDifference(nums []int, k int) int {
slices.Sort(nums)
ans := math.MaxInt
for i := k - 1; i < len(nums); i++ {
ans = min(ans, nums[i]-nums[i-k+1])
}
return ans
}

var minimumDifference = function(nums, k) {
nums.sort((a, b) => a - b);
let ans = Infinity;
for (let i = k - 1; i < nums.length; i++) {
ans = Math.min(ans, nums[i] - nums[i - k + 1]);
}
return ans;
};

impl Solution {
pub fn minimum_difference(mut nums: Vec<i32>, k: i32) -> i32 {
nums.sort_unstable();
let k = k as usize;
let mut ans = i32::MAX;
for i in k - 1..nums.len() {
ans = ans.min(nums[i] - nums[i - k + 1]);
}
ans
}
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n\log n)$，其中 $n$ 是 $\textit{nums}$ 的长度。瓶颈在排序上。
• 空间复杂度：$\mathcal{O}(1)$。忽略排序的栈开销。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

你可能猜了一个结论：把最小的数和最大的数配对，把第二小的数和第二大的数配对，依此类推。注意题目保证 $n$ 是偶数。

但是，如何证明这样做是对的？

设 $\textit{nums}$ 排序后的结果为 $a_1\le a_2\le \cdots \le a_n$。

首先证明，$a_1$ 与 $a_n$ 配对是最优的。

设 $a_i$ 和 $a_j$ 是数组中的另外两个数，考虑如下两种配对方案：

• $(a_1,a_i)$ 和 $(a_j,a_n)$。最大数对和为 $M_1 = \max(a_1+a_i,a_j+a_n,其他数对和)$。
• $(a_1,a_n)$ 和 $(a_i,a_j)$。最大数对和为 $M_2 = \max(a_1+a_n,a_i+a_j,其他数对和)$。

由于 $a_1\le a_j$，$a_i\le a_n$，所以 $a_1+a_i\le a_j+a_n$，所以 $M_1 = \max(a_j+a_n,其他数对和)$。

由于 $a_1+a_n\le a_j+a_n$ 且 $a_i+a_j\le a_j+a_n$，所以 $\max(a_1+a_n,a_i+a_j)\le a_j+a_n$，所以 $M_2\le M_1$。

这意味着，对于任意最优配对方案，将其调整为 $a_1$ 和 $a_n$ 配对，不会让最大数对和变得更大。所以存在最优配对方案，其中 $a_1$ 和 $a_n$ 是配对的。

去掉 $a_1$ 和 $a_n$（已配对），问题变成一个规模更小的子问题（$n-2$ 个数），同理可得其他数的配对方式。

class Solution:
    def minPairSum(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        return max(nums[i] + nums[-1 - i] for i in range(n // 2))

class Solution {
    public int minPairSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int ans = 0;
        for (int i = 0; i < n / 2; i++) {
            ans = Math.max(ans, nums[i] + nums[n - 1 - i]);
        }
        return ans;
    }
}

class Solution {
public:
    int minPairSum(vector<int>& nums) {
        ranges::sort(nums);
        int n = nums.size();
        int ans = 0;
        for (int i = 0; i < n / 2; i++) {
            ans = max(ans, nums[i] + nums[n - 1 - i]);
        }
        return ans;
    }
};

#define MAX(a, b) ((b) > (a) ? (b) : (a))

int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int minPairSum(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), cmp);
    int ans = 0;
    for (int i = 0; i < numsSize / 2; i++) {
        ans = MAX(ans, nums[i] + nums[numsSize - 1 - i]);
    }
    return ans;
}

func minPairSum(nums []int) (ans int) {
slices.Sort(nums)
n := len(nums)
for i, x := range nums[:n/2] {
ans = max(ans, x+nums[n-1-i])
}
return
}

var minPairSum = function(nums) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    let ans = 0;
    for (let i = 0; i < n / 2; i++) {
        ans = Math.max(ans, nums[i] + nums[n - 1 - i]);
    }
    return ans;
};

impl Solution {
    pub fn min_pair_sum(mut nums: Vec<i32>) -> i32 {
        nums.sort_unstable();
        let n = nums.len();
        let mut ans = 0;
        for i in 0..n / 2 {
            ans = ans.max(nums[i] + nums[n - 1 - i]);
        }
        ans
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n\log n)$，其中 $n$ 是 $\textit{nums}$ 的长度。瓶颈在排序上。
• 空间复杂度：$\mathcal{O}(1)$。忽略排序的栈开销。

专题训练

见下面贪心题单的「§1.2 单序列配对」和「§1.7 交换论证法」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府