P1119

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

题解：洛谷P1119 灾后重建 题目传送门 前言：没有掌握floyed求最短路的精髓是每次增加选一个中转点，导致写了2h才勉强卡过 法1：最暴力的想法就是开个三维数组把前i个点的dis状态全部存下来，跑N次floyed，当然由于每次点数时递增的，所以实际复杂度远远小于O(N^4)，算了下大概200个 ......

题目传送：链接 思路 算法：\(Floyd.\) 每次询问记录一个变量 \(n\)，表示当前遍历到哪个点。 当 \(t_n <= T\) 的时候，利用 \(n\) 点更新到 $(x,y) $ 点的最短路。 如果发现 \(x,y\) 点其中有一个还没有修好，或者是 \(d_{x_y}\) 为 0x3f ......

### [在洛谷中查看](https://www.luogu.com.cn/problem/P1119) ### 解法1（我想的解法，不完全正确）: 很常见的套路：将询问按时间排序。时间复杂度：$O(\;q\,(n\,logn+m)\;)$，即 $10^9$，开 $O2$ 才能过。 ~~非常麻烦有没 ......

题目地址 题意：给出n个村庄的灾后重建所需时间和m条双向路和它们的路径长，进行q次询问，每次询问两个村庄在时间t时的最短的路径，且路径上所有村庄都已重建，如果不存在或者t时两个村庄都未重建好输出-1 Solution floyd算法板子题 dp[i][j][k]表示从i中转k到j的最短距离 根据fl ......