2024-12-30 17:16 门头沟学院 C++ 发布于江西
关注
day61
Floyd多源最短路：
思路：动态规划
1、grid[i][j][k] = m，表示 节点i 到 节点j 以[1...k] 集合为中间节点的最短距离为m；
2、递推公式：
节点i 到 节点j 的最短路径经过节点k：grid[i][j][k] = grid[i][k][k - 1] + grid[k][j][k - 1]
节点i 到 节点j 的最短路径不经过节点k：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])
3、初始化：
for(int i = 0; i < m; i++){
cin >> p1 >> p2 >> val;
grid[p1][p2][0] = val;
grid[p2][p1][0] = val; // 注意这里是双向图
}
4、遍历顺序：k一定要放在最外层
思路：动态规划
1、grid[i][j][k] = m，表示 节点i 到 节点j 以[1...k] 集合为中间节点的最短距离为m；
2、递推公式：
节点i 到 节点j 的最短路径经过节点k：grid[i][j][k] = grid[i][k][k - 1] + grid[k][j][k - 1]
节点i 到 节点j 的最短路径不经过节点k：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])
3、初始化：
for(int i = 0; i < m; i++){
cin >> p1 >> p2 >> val;
grid[p1][p2][0] = val;
grid[p2][p1][0] = val; // 注意这里是双向图
}
4、遍历顺序：k一定要放在最外层
全部评论
相关推荐
查看30道真题和解析 2025-12-14 11:43
黑龙江大学 Java 
用微笑面对困难：确实比较烂，可以这么修改：加上大学的qs排名，然后大学简介要写一些，然后硕士大学加大加粗，科研经历第一句话都写上在复旦大学时，主要负责xxxx，简历左上角把学校logo写上，建议用复旦大学的简历模板
点赞 评论 收藏
分享