题目链接P1119灾后重建先读题意，就是求在\(t\)时间时当前\(a\)到\(b\)的最短路，并且当前\(a\)和\(b\)村都必须重建完毕。即然一两点间距离。再看一眼数据范围，可以知道需要用到Floyd算法。比较暴力的，可能会用\(n\)次Floyd把每次时间的两点间距算出，但这样是\(O(n^

目录思路代码\(原题传送门\)思路首先先来分析一下算法，Floyd算法的时间复杂度是\(O(n^3)\)虽然很多，但在这一题里很合适。dijkstra算法用堆优化的时间复杂度是\(O(m\logn)\)，在这一题里会超时。Bellman–Ford算法的时间复杂度是\(O(mn)\)，会超时。所以说这一题是能用Flo

floyd算法是图论中较为简单的最短路算法，但在某些方面远超最短路范围。算法思路定义\(f[x][y]\)为\(x\)到\(y\)节点的最短路径。初始化：若存在边\((x,y)\)则\(f[x][y]\)等于边长度；若不存在，为\(+\infty\)。特别的，\(f[x][x]=0\)。我们考虑一下，\(x,y\)这两个节点通

原题链接思路请看题解，讲的非常详细，细节请看我一道很多细节的题1.初始化要赋1e92.只有在两个村庄都重建完之后，一条路才通3.一条路都通了之后，两个村庄都要再走一遍4.村庄编号从0开始，而不是从1开始5.弹出重建完成的村庄时，迭代器it记得加上判断不超过n，因为t为零时永远小于when