当前位置：首页 > article >正文

卡码网KamaCoder 97. 小明逛公园

article 2025/1/26 20:40:03

题目来源：97. 小明逛公园

C++题解（来源代码随想录）：Floyd 算法

动规五部曲：

确定dp数组（dp table）以及下标的含义

grid[i][j][k] = m，表示节点i 到节点j 以[1...k] 集合为中间节点的最短距离为m。节点i 到节点j 中间一定经过很多节点，那么你能用什么方式来表述中间这么多节点呢？所以这里的k不能单独指某个节点，k 一定要表示一个集合，即[1...k] ，表示节点1 到节点k 一共k个节点的集合。

确定递推公式

我们分两种情况：

节点i 到节点j 的最短路径经过节点k
节点i 到节点j 的最短路径不经过节点k

对于第一种情况，grid[i][j][k] = grid[i][k][k - 1] + grid[k][j][k - 1]

节点i 到节点k 的最短距离是不经过节点k，中间节点集合为[1...k-1]，所以表示为grid[i][k][k - 1]；节点k 到节点j 的最短距离也是不经过节点k，中间节点集合为[1...k-1]，所以表示为 grid[k][j][k - 1]

第二种情况，grid[i][j][k] = grid[i][j][k - 1]

因为我们是求最短路，即： grid[i][j][k] = min(grid[i][k][k - 1] + grid[k][j][k - 1]， grid[i][j][k - 1])

dp数组如何初始化

grid[i][j][k] = m，表示节点i 到节点j 以[1...k] 集合为中间节点的最短距离为m。刚开始初始化k 是不确定的。把k 填成1，那如何上来就知道节点2 经过节点1 到达节点6的最短距离是多少呢。所以只能把k 赋值为 0，本题节点0 是无意义的，节点是从1 到 n。

这样我们在下一轮计算的时候，就可以根据 grid[i][j][0] 来计算 grid[i][j][1]，此时的 grid[i][j][1] 就是节点i 经过节点1 到达节点j 的最小距离了。

确定遍历顺序

从递推公式：grid[i][j][k] = min(grid[i][k][k - 1] + grid[k][j][k - 1]， grid[i][j][k - 1]) 可以看出，我们需要三个for循环，分别遍历i，j 和k

而 k 依赖于 k - 1， i 和j 的到并不依赖与 i - 1 或者 j - 1 等等。

我们把 k =0 的 i 和j 对应的数值都初始化了，这样才能去计算 k = 1 的时候 i 和 j 对应的数值。所以遍历k 的for循环一定是在最外面，这样才能一层一层去遍历。

举例推导dp数组

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<vector<int>> grid(n + 1, vector<int>(n + 1, 10005));  // 因为边的最大距离是10^4

    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        grid[p1][p2] = val;
        grid[p2][p1] = val; // 注意这里是双向图

    }
    // 开始 floyd
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j]);
            }
        }
    }
    // 输出结果
    int z, start, end;
    cin >> z;
    while (z--) {
        cin >> start >> end;
        if (grid[start][end] == 10005) cout << -1 << endl;
        else cout << grid[start][end] << endl;
    }
}

使用二维数组grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j]); 可以看成贪心算法，节点 i 到节点 j 是否经过节点 k ，进而更新grid[i][j]

查看全文

http://www.kler.cn/a/369830.html