企业官网建设流程全解析

做最短路题最怕遇到什么？图特别大，却让你把点对之间的答案都算出来。CF 1196F 就是这道题：点数 N 和边数 M 都能跑到 2e5，K 却只有 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_{K+1} ≥ w_K。由于所有边权都是正数，P 的总长度至少为 w(e)，于是：

len(P) ≥ w(e) ≥ w_K ≥ L_K

前 K 条单边路径里至少有 K 条路径的长度都不超过 w_K，也就是说至少有 K 条路径的长度不超过 len(P)。这样的话，P 在集合中的排名最多是第 K+1，不可能排到第 K。矛盾。

所以结论成立：排名第 K 的路径，其所有边一定都在边权最小的 K 条边里。

这个证明的关键是“边权为正”和“单边也是路径”这两个条件。算法题里这种不起眼的性质往往才是真正的突破口。

2. 离散化：把 2e5 压到 800

2.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. 在这个小图上跑 Floyd

3.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; vector<Edge> 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); vector<int> nodes; vector<Edge> 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(); vector<vector<long long>> dist(cnt, vector<long 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]; } } } } vector<long 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 ≤ 2K，Floyd 是 O(K^3)。收集点对距离并排序，点对数量 O(K^2)，排序 O(K^2 log K)。总复杂度：

O(M log M + K^3)

K 最大 400，K^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 离散化到 800，Floyd 就地复活。

如果再往深一点想，这个“前 K 小边”思路还有扩展空间。如果题目改成求第 K 小点对距离中每一条路径的具体构成，就需要额外记录路径的前驱。Floyd 的pre[i][j]可以在转移时更新，复杂度不变，但这道题的输出只需要长度，就没必要写了。我实际练习时经常把这个条件放宽，顺手写一个路径还原版本，用来加深对 Floyd 动态规划过程的理解。做题嘛，AC 只是起点，把每一步为什么成立想明白，才算真正吃透。