做最短路题最怕遇到什么图特别大却让你把点对之间的答案都算出来。CF 1196F 就是这道题点数 N 和边数 M 都能跑到 2e5K 却只有 400问题偏偏是“所有点对最短路径中第 K 小的路径长度”。第一反应是全源最短路但 Floyd 的 O(N^3) 在这种数据规模面前完全是天文数字。别急着放弃这道题的精髓就在“离散化”三个字上——你根本不需要关心全图只需要把最有可能成为答案的那一小撮边拿出来在一个袖珍图上跑 Floyd 就行。这道题适合谁看正在刷 Codeforces 图论题的选手、准备面试或者打周赛时被“大图小 K”类问题卡住的人还有想搞清楚“什么时候该离散化什么时候不该离散化”的人。题目本身是 CF 1196F难度不算高但思路非常干净先用一个小观察把图的规模从 2e5 砍到 800 以内再跑一次 Floyd把答案排序取第 K 个。下面我完整拆一遍思路、证明、代码和坑。1. 题目到底在问什么1.1 原始题意给定一个带权无向图N 个点M 条边每条边有正整数边权。定义“路径长度”为路径上所有边权之和。题目要求在所有点对之间的最短路径中找出长度第 K 小的那一条输出它的长度。这里有一个容易被忽略的细节不是让你求“从某个点出发的第 K 短路径”而是把所有无序点对、所有可能的路径全部摊开取所有点对最短路径这个集合里的第 K 小元素。数据范围有一个决定性条件K 不超过 400。N 和 M 都可以到 2e5。这意味着如果直接对全图做最短路单次 Dijkstra 是 O(M log N)做 N 次就直接爆炸多源 Floyd 更是连想都别想。1.2 已知结论答案只可能来自最小的 K 条边这道题的题解里有句经典结论把所有边按边权从小到大排序取前 K 条边答案一定由这些边构成。这个结论不是“显然成立”的运气型观察而是有严格证明的。我第一次看到这个结论时也愣了一下后来仔细推才发现它依赖一个非常朴素的事实每条边本身也是一条合法路径。证明思路如下。设第 K 小的边权为 w_K。前 K 条边各自作为单边路径已经构成了 K 条不同的路径每条路径的长度就是这条边的边权都不超过 w_K。因此第 K 小的路径长度 L_K 一定满足L_K ≤ w_K假设某条路径 P 是最短路径集合中第 K 小的那条但 P 包含一条不在前 K 条最小边里的边 e。那么 e 的边权 w(e) ≥ w_{K1} ≥ w_K。由于所有边权都是正数P 的总长度至少为 w(e)于是len(P) ≥ w(e) ≥ w_K ≥ L_K前 K 条单边路径里至少有 K 条路径的长度都不超过 w_K也就是说至少有 K 条路径的长度不超过 len(P)。这样的话P 在集合中的排名最多是第 K1不可能排到第 K。矛盾。所以结论成立排名第 K 的路径其所有边一定都在边权最小的 K 条边里。这个证明的关键是“边权为正”和“单边也是路径”这两个条件。算法题里这种不起眼的性质往往才是真正的突破口。2. 离散化把 2e5 压到 8002.1 参与的点最多只有 2K 个既然答案只由前 K 条边组成那么真正需要参与计算的图就只有这些边和它们的端点。前 K 条边最多涉及 2K 个不同的顶点因为每条边贡献两个端点可能有重复。K ≤ 400所以最多 800 个点。800 这个规模对 Floyd 来说非常友好。O(800^3) 大约是 5.12 亿次内层操作在 C 的编译优化下配合剪枝CF 的数据是完全能跑的。如果老老实实对 2e5 个点跑 Floyd那会跑到宇宙热寂。这一步就是离散化的动机不是“为了用 Floyd 而强行离散化”而是“答案相关的点本身就很少离散化只是把图搬到这个小集合上”。2.2 离散化具体怎么做实际操作分三步。第一步读入所有边按边权升序排序。第二步取前 K 条边把每条边的两个端点放进一个临时数组顺便记录边本身。第三步对端点数组去重、排序然后用下标映射成 0 到 cnt-1 的紧凑编号其中 cnt 是不同端点数。这个过程不需要 map直接排序去重再加 lower_bound 就行。端点总数最多 800就算用最朴素的 O(cnt^2) 查找也毫无压力。代码里一般用一个结构体存边struct Edge { int u, v; long long w; bool operator(const Edge other) const { return w other.w; } };排序用sort(edges.begin(), edges.end());前 K 条边就存在edges[0]到edges[K-1]。注意 K 可能比 M 大严谨一点应该写int take min(K, M)把 take 当作真正要取的数量。不过 CF 原题的数据基本不会卡这个边界但写代码时养成习惯没坏处。2.3 邻接矩阵的初始化离散化完成后开一个 cnt × cnt 的 long long 矩阵dist全部初始化为 INF对角线dist[i][i] 0。然后遍历取出来的每条边在两个离散化后的顶点之间建边。注意是无向图所以dist[a][b] min(dist[a][b], w); dist[b][a] min(dist[b][a], w);如果有多条边连接同一个点对取最小值。这个min不是可有可无的重边在 CF 数据集里经常出现不处理会得到错误答案。到这里原图已经被压缩成一个最多 800 点的小带权无向图接下来所有工作都在这个图上进行。3. 在这个小图上跑 Floyd3.1 为什么 Floyd 够用很多同学纠结为什么不用 Dijkstra 或 SPFA Floyd 的复杂度是 O(cnt^3)当 cnt 接近 800 时确实不低但好处是无脑、简单、不容易写错而且 codeforces 的时限和评测机通常能扛住。还有一个重要原因Floyd 天然就是全源最短路一次跑完就能得到所有点对之间的最短距离。如果换成 N 次 Dijkstra虽然复杂度可能更优但代码量和出错概率都会上升。竞赛里“够用”和“最优”之间我优先选不会出错的。800^3 大约 5 亿次运算加上剪枝和-O2一般能在一秒多到两秒完成。如果担心超时可以在内层跳过 INF 的无效计算。后面代码里我会写出来。3.2 枚举顺序不能乱Floyd 的标准枚举顺序是for (int k 0; k cnt; k) for (int i 0; i cnt; i) for (int j 0; j cnt; j) dist[i][j] min(dist[i][j], dist[i][k] dist[k][j]);最外层是中间节点 k不是起点 i。很多人初学 Floyd 时记不住这个顺序把 k 放内层结果算出来的不是最短路。为什么必须 k 在外层因为 Floyd 是动态规划思想dist[i][j]表示“允许经过前 k 个中间节点时i 到 j 的最短路”。推导关系是dist_k[i][j] min(dist_{k-1}[i][j], dist_{k-1}[i][k] dist_{k-1}[k][j])也就是说k 作为维度信息必须一层一层地扩展。如果把 k 放内层相当于所有点对同时尝试所有中间点但缺少“中间点集合逐步扩大”的顺序约束可能会在错误的状态上做转移。3.3 收集答案Floyd 跑完后dist[i][j]存的就是离散化后所有点对之间的最短路径长度。原题要求第 K 小所以需要把这些距离全部收集起来排序。注意一点无向图最短路径是对称的dist[i][j] dist[j][i]收集时只取i j的对避免重复。把收集到的值放进 vector排个序输出ans[K-1]。如果 cnt 特别小导致点对数量小于 K怎么办稳妥起见可以取 vector 的最后一个元素作为答案。不过在 CF 原题的数据范围内只要 K ≤ 400 且图连通性满足题目隐含条件基本不会出现这种情况。4. 完整 C 实现4.1 代码直接上一版能 AC 的参考实现。没有用任何花哨技巧适合当成模板理解。#include bits/stdc.h using namespace std; const long long INF 4e18; struct Edge { int u, v; long long w; bool operator(const Edge other) const { return w other.w; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M, K; cin N M K; vectorEdge edges(M); for (int i 0; i M; i) { cin edges[i].u edges[i].v edges[i].w; --edges[i].u; --edges[i].v; } sort(edges.begin(), edges.end()); int take min(K, M); vectorint nodes; vectorEdge selected; for (int i 0; i take; i) { nodes.push_back(edges[i].u); nodes.push_back(edges[i].v); selected.push_back(edges[i]); } sort(nodes.begin(), nodes.end()); nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end()); int cnt nodes.size(); vectorvectorlong long dist(cnt, vectorlong long(cnt, INF)); for (int i 0; i cnt; i) { dist[i][i] 0; } for (const auto e : selected) { int a lower_bound(nodes.begin(), nodes.end(), e.u) - nodes.begin(); int b lower_bound(nodes.begin(), nodes.end(), e.v) - nodes.begin(); if (e.w dist[a][b]) { dist[a][b] dist[b][a] e.w; } } for (int k 0; k cnt; k) { for (int i 0; i cnt; i) { if (dist[i][k] INF) continue; for (int j 0; j cnt; j) { if (dist[k][j] INF) continue; if (dist[i][k] dist[k][j] dist[i][j]) { dist[i][j] dist[i][k] dist[k][j]; } } } } vectorlong long all; for (int i 0; i cnt; i) { for (int j i 1; j cnt; j) { all.push_back(dist[i][j]); } } sort(all.begin(), all.end()); cout all[K - 1] endl; return 0; }4.2 复杂度分析排序 M 条边是 O(M log M)。取前 K 条后点数 cnt ≤ 2KFloyd 是 O(K^3)。收集点对距离并排序点对数量 O(K^2)排序 O(K^2 log K)。总复杂度O(M log M K^3)K 最大 400K^3 约 6.4e7如果算上常数和 cnt 到 800 时的 5.12e8整体在 CF 的评测环境下仍然可行。空间是 O(K^2) 的邻接矩阵完全不用担心。5. 常见问题与排查心得5.1 INF 怎么选才安全这是这道题最容易翻车的地方。边权最大值可以到 1e9路径可能经过很多条边最坏情况下长度能到 2e14 级别。如果 INF 用 int 的 0x3f3f3f3f也就是 10 亿出头根本盖不住真实距离Floyd 里一比较就出错。我习惯把 INF 定义成4e18配合 long long 使用。这样有两个好处一是比任何可能出现的真实距离都大得多二是在代码里做dist[i][k] dist[k][j]前先判断是否为 INF避免两个 INF 相加溢出。有些人的写法是不判断 INF 直接加法那 INF 就必须小于 9e18 的一半否则 long long 直接爆掉。为了省心我在 Floyd 内层加了两行跳过判断既安全又带一点剪枝加速效果。5.2 点对数量不足 K 个的边界如果 cnt 很小例如只有两个点那么点对只有一个all的长度是 1代码里的all[K-1]会数组越界。这种情况在 CF 1196F 的原题数据里几乎不会出现因为题目要求保证存在第 K 短路径。但如果是自己出数据、或者把代码改成通用工具最好加一个保护if ((int)all.size() K) { cout all.back() endl; } else { cout all[K - 1] endl; }当点对数量不足 K 时理论上应该说“第 K 小不存在”但按竞赛题的隐含约定这种情况默认不会发生。保护逻辑可以帮你避免 RE但不能帮你解决题目本身无解的问题。5.3 重边和自环无向图的重边一定要用min处理。虽然我们选的是前 K 条最小边但同一个点对可能会出现多条边邻接矩阵一个位置只能存一个最短距离直接用赋值操作覆盖会丢掉更短的路。自环在本题中不需要特殊处理因为dist[i][i]已经初始化成 0就算有自环也不会影响答案。唯一要注意的是路径长度必须是正数如果题目出现负权边整个“第 K 短只依赖前 K 小边”的证明就不成立了因为负权边可能出现在很长的路径里让总长度变小。CF 1196F 保证边权为正所以没问题。5.4 Floyd 中途的剪枝技巧上面代码里if (dist[i][k] INF) continue; if (dist[k][j] INF) continue;这两个判断表面上看只是防溢出实际上对性能帮助也不小。小图 INF 的占比很高尤其是图不连通的时候大量点对之间根本没有路。跳过这些完全无效的转移能省下不少计算。800^3 是 5.12 亿次剪枝后实际进入内层执行的次数可能只有几分之一。如果你还想更快可以做一个极端优化把邻接矩阵换成一维数组用long long*存储再调整循环顺序让内存访问尽量连续。不过对 K ≤ 400 的数据原版代码已经足够没必要把自己搞晕。5.5 为什么不去掉 Floyd 而用 Dijkstra 堆优化cnt 只有 800理论上对每个点跑一次 Dijkstra复杂度 O(cnt * (cnt log cnt))比 Floyd 快很多。那题解为什么清一色 Floyd原因很简单Floyd 好写、不容易错、实现逻辑短。在这种“反正 800 个点怎么跑都能过”的规模下优先选代码正确性风险最低的方案。竞赛不是展示最优算法的地方是展示“用最少 bug 拿分”的地方。如果你自己写 Dijkstra 很稳也可以换但没必要。Floyd 的对称性、全源性和零调试成本在这个数据范围里就是最优解。5.6 代码里nodes去重后的查询方式因为 cnt 很小我用lower_bound在去重后的 vector 上做映射。这个操作每次 O(log cnt)总共执行 O(K) 次完全无所谓。甚至写双重循环暴力找索引也能过。唯一的教训是不要把原编号直接当成下标用离散化后一定要通过映射获取新下标否则矩阵大小和实际索引会对不上。6. 这道题最值得记住的两个点第一个是“用前 K 小边缩小图规模”的思路。它不依赖 Floyd而是依赖“单边路径已经是很强的候选答案”这个直觉。遇到其它数据范围类似的问题比如第 K 短路、第 K 小点对距离、甚至带限制的图论问题都可以先想想能不能从全局信息里切出一小部分让计算只在这部分上进行。第二个是“什么时候适合用 Floyd”。很多教材喜欢强调 Floyd 是 O(N^3) 的垃圾算法但它在 N 小于等于 800 时其实是非常好用的工具。与其背一堆复杂算法不如先学会判断图的规模。像本题这样把 N 离散化到 800Floyd 就地复活。如果再往深一点想这个“前 K 小边”思路还有扩展空间。如果题目改成求第 K 小点对距离中每一条路径的具体构成就需要额外记录路径的前驱。Floyd 的pre[i][j]可以在转移时更新复杂度不变但这道题的输出只需要长度就没必要写了。我实际练习时经常把这个条件放宽顺手写一个路径还原版本用来加深对 Floyd 动态规划过程的理解。做题嘛AC 只是起点把每一步为什么成立想明白才算真正吃透。