思路分析 题意 给定一张 nnn 个点、mmm 条边的无向带权图，求所有点对最短路中第 kkk 小的值。 数据范围的矛盾与突破口 * nnn 高达 2×1052 \times 10^52×105，做全源最短路（如 Floyd O(n3)O(n^3)O(n3)）根本不可能 * 但 k≤400k \leq 400k≤400 非常小——这是突破口 关键推导（为什么只取前 KKK 条边就够了） 1. 将所有边按权值从小到大排序，记第 iii 条边权值为 wiw_iwi 2. 前 kkk 条边给出了 kkk 个不同的点对 (ui,vi)(u_i, v_i)(ui ,vi )，每对之间的最短路 d(ui,vi)≤wi≤wkd(u_i, v_i) \leq w_i \leq w_kd(ui ,vi )≤wi ≤wk 3. 所以至少有 kkk 个最短路 ≤wk\leq w_k≤wk ，即第 kkk 小的最短路 ≤wk\leq w_k≤wk 4. 对于任何长度 ≤wk\leq w_k≤wk 的最短路，其路径上的每一条边权值都 ≤wk\leq w_k≤wk ，而权值 ≤wk\leq w_k≤wk 的边一定在排序后的前 kkk 条里 5. 因此，前 kkk 条边已经包含了所有我们关心的最短路需要的全部信息 缩图规模 前 kkk 条边最多涉及 2k=8002k = 8002k=800 个节点，对这些节点跑 Floyd 即可：8003≈5×108800^3 \approx 5 \times 10^88003≈5×108，刚好能过。 算法流程 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码