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一定要放在最外层
全部评论
相关推荐
点赞 评论 收藏
分享
02-24 17:40
门头沟学院 Java 等闲_：https://www.nowcoder.com/share/jump/469255111772017977737。原主的帖子在这里
查看24道真题和解析 点赞 评论 收藏
分享
那场寒冬：字节入职后完全看组有没有hc，暑假实习只是一个名字
点赞 评论 收藏
分享