Open nagato1208 opened 5 years ago
https://nagato1208.github.io/2019/09/05/codeforces-295B-Greg-and-Graph/#more
描述对于一个邻接矩阵表示的有向完全图, 我们有一个节点删除序列(最终会删完所有节点). 以这个序列的顺序进行删除, 求出在每次删除之前, 所有(连通的)点对的最短路之和.节点数量最多500个. 思路需要深入理解floyd算法… 最外层的k的作用是, 用来标定以k为中间节点, i和j的最短路是什么. 那么对于删掉的节点, 已经不存在了, 最短路不能再经过它.这样我们可以逆序进行一次多源最短路搜索.
https://nagato1208.github.io/2019/09/05/codeforces-295B-Greg-and-Graph/#more
描述对于一个邻接矩阵表示的有向完全图, 我们有一个节点删除序列(最终会删完所有节点). 以这个序列的顺序进行删除, 求出在每次删除之前, 所有(连通的)点对的最短路之和.节点数量最多500个. 思路需要深入理解floyd算法… 最外层的k的作用是, 用来标定以k为中间节点, i和j的最短路是什么. 那么对于删掉的节点, 已经不存在了, 最短路不能再经过它.这样我们可以逆序进行一次多源最短路搜索.