企业官网建设流程全解析

题目名字叫 K-th Path，编号是 CodeForces 1196F，看到这个标签你会立刻想到 Floyd 和离散化的组合。当时我第一反应是：求所有路径里第 k 短的路径长度？这不是得做全源最短路再排序？可再扫一眼数据范围，n、m 都是 2e5，k 却只有 400。这个反差基本把答案写在了脸上——不需要碰原图的 2e5 个点，只需要围绕前 k 条边做文章。这篇文章就把这套 Floyd + 离散化的思路完整拆开，从为什么只取前 k 条边，到怎么压缩顶点、跑全源最短路、收集答案，最后聊几个我实际提交时踩过的坑。适合已经会最短路基础、想弄明白这类“图很大但答案规模很小”的题的同学。

1. 这题到底在问什么：K-th Path 的题面与隐含信号

1.1 题面细节和 k≤400 的含义

题目给的图是 n 个点、m 条边的无向带权图，边权都是正数。定义一条路径的长度是路径上所有边的权重之和，路径的起点和终点可以任意选择，不需要从某个固定编号出发。我们要做的事是：把所有合法的路径按长度从小到大排序，然后输出第 k 小的那个长度值。

这里有一个很容易被忽略的点：路径并不是“最短路”，而是所有路径都算数。比如两点之间如果有一条直连边权值为 10，但绕一下经过另一个点总长 7，那么 7 和 10 都算两条不同的路径，都要参与排序。所以题目本质上是在问：这张图里所有可能的“连线长度”排序后，第 k 个小的值是什么。

真正的突破口不是图有多大，而是 k 的大小。k ≤ 400，而 n、m 可以到 2e5。如果一上来就对 n 个点做全源最短路，连存矩阵的空间都不够；如果对每个点跑一遍 Dijkstra，一次就是 O(m log n)，乘上 n 直接不可能。枚举所有路径更是指数级别的笑话。所以题目唯一能利用的就是“k 很小”这个条件，它暗示答案对应的路径不会用到太多大权边，候选集合可以被压缩到 O(k) 的规模。

1.2 为什么暴力枚举不可行

我们先简单感受一下暴力的下场。假设图里有 10 个点，点之间两两都有边，那简单路径的数量会随着边长指数爆炸。就算只考虑 6~7 个点以内的路径，你也需要 DFS 每个起点、每次扩展所有邻点，同时还要维护访问标记。等图扩大到 2e5 个点，这条路彻底走不通。

再看全源最短路。Floyd 需要 V × V 的矩阵，2e5 个点意味着 4e10 个状态，空间直接超限；即使换成稀疏图的 Johnson 算法，先把边权改造一遍，再对每个点跑 Dijkstra，时间复杂度也要 O(nm log n) 级别，同样不可能。

所以看到 k ≤ 400 时应该立刻想到：答案只和排序后靠前的那批边有关，和后面那些大边没关系。这个直觉先记下，下一节给出严格证明。

2. 从 2e5 到 400：取前 k 条边的正确性证明

2.1 第 k 短路径不会使用“大边”

把所有权边按权重从小到大排序，记第 k 小的边权为 w_k。为什么这个 w_k 这么关键？因为每条边单独本身就是一条合法路径，长度为该边的权重。所以图中至少有 k 条路径的长度不超过 w_k，也就是前 k 条“单边路径”。既然已经有 k 条路径能把长度压到 w_k 以内，那么真正要找的第 k 短路径长度 L 一定满足 L ≤ w_k。

接下来用反证法：假设有一条路径 P，它包含了某条权重 w > w_k 的边。由于所有边权都是正数，P 的总长度一定 ≥ w > w_k ≥ L。这意味着 P 的长度严格大于第 k 短路径的理论上界，根本不可能排到前 k 名里。换句话说，第 k 短路径里的任何一条边，权重都不可能超过 w_k。

这个结论的价值在于：我们不需要看完整张图，只需要保留所有权值 ≤ w_k 的边，第 k 短路径的所有边就都在里面了。为了把规模压到最小，排序后直接取前 k 条边即可。

我当初第一次看题解时，对“单边路径”这个观察印象特别深。它把一道看似全源最短路的问题，瞬间降维成“挑小边”的问题。很多新手会忽略：既然任意一条边都能单独作为路径候选，那答案的上界就天然被第 k 小的边权卡死了。

2.2 同权边处理与取边策略

直接取前 k 条边有个理论上的小坑：如果排序后有很多边的权重都等于 w_k，那么前 k 条边的边界是模糊的，C++ sort 并不会保证同权边的相对顺序。你取到的是哪 k 条同权边，可能会略有区别。

那取前 k 条会不会漏答案？分两种情况看。如果漏掉的同权边恰好组成了第 k 短路径的一部分，而选中的 k 条边里没有这条，答案会不会变？很多人担心这个。实际上，因为我们已经保底有 k 条单边路径，长度不超过 w_k，答案 L 大概率由更小的路径决定；如果所有候选路径长度都等于 w_k，漏掉一条同权边可能少一个候选，但题目保证第 k 短路径存在，所以通常不会出问题。

不过我在写代码时还是习惯稍微严谨一点：排序取第 k 小边权 w_k，然后用 while 循环把所有权值 ≤ w_k 的边都收进来。这样即使同权边泛滥，也能保证不丢边。代价是顶点数量可能会比 2k 多一点点，但多出来的也只是“并列第 k”的那些点，规模依然可控。

补充一个边界：如果 m < k，那就把所有边都保留下来。此时最多也只有 m 条边，点数最多 2m < 800，依然满足 O(k) 的范畴。

3. 离散化建图：把稀疏图压进邻接矩阵

3.1 顶点压缩的具体流程

保留的边最多只有 k 条，每条边两个端点，所以涉及的顶点数量最多是 2k，也就是 800。原图的编号可能是 1 到 2e5 的任意值，直接拿原编号当矩阵下标肯定不行，必须做离散化。

操作流程很固定：

1. 读入所有边，存到结构体数组里。
2. 按边权从小到大排序。
3. 保留前 keep 条边，keep = min(m, k)。
4. 把保留边的所有端点塞进 vector。
5. 排序去重，得到 V 个不同顶点。
6. 建立原编号到 0..V-1 的映射。

映射这部分，因为题目保证 n ≤ 2e5，我一般直接开一个 int id[n+1] 数组，初始化为 -1，然后给每个出现过的点分配新编号。这样比 unordered_map 更快，也不会出现哈希冲突的问题。

vector<int> pts; for (int i = 0; i < keep; i++) { pts.push_back(edges[i].u); pts.push_back(edges[i].v); } sort(pts.begin(), pts.end()); pts.erase(unique(pts.begin(), pts.end()), pts.end()); int V = pts.size(); vector<int> id(n + 1, -1); for (int i = 0; i < V; i++) { id[pts[i]] = i; }

这里有个小细节：排序去重之前一定要把端点 append 完整，不要把 u 和 v 弄混。我一开始犯过只收集了 u、忘了 v 的错，结果建出来的图缺了一半边，Floyd 跑完答案明显偏大。

3.2 初始化矩阵与重边合并

离散化完成之后，邻接矩阵的大小就只有 V × V 了。V 最大 800，开一个二维 long long 数组毫无压力。

矩阵初始化：对角线为 0，其余为 INF。然后遍历保留的边，把 (id[u], id[v]) 的权值写进去。注意是无向图，要同时写 dist[u][v] 和 dist[v][u]。如果有重边，取最小权值，因为 Floyd 需要的是两点之间的最短距离，重边里只有最小的那条会参与后续松弛。

为什么用 long long？单条边权最大可以到 1e9，一条路径可能包含几百条边，总长度会超过 int 范围。用 int 存 INF 也可能递归溢出，直接开 long long 最稳妥。

const long long INF = 4e18; vector<vector<long long>> dist(V, vector<long long>(V, INF)); for (int i = 0; i < V; i++) dist[i][i] = 0; for (int i = 0; i < keep; i++) { int u = id[edges[i].u]; int v = id[edges[i].v]; long long w = edges[i].w; if (w < dist[u][v]) { dist[u][v] = dist[v][u] = w; } }

如果觉得 vector<vector > 访问不够快，也可以直接开静态数组 long long d[805][805]，因为 V 最大不会超过 800。静态数组在三层循环里的缓存友好度和寻址速度都更好，竞赛代码里推荐后者。

4. 跑 Floyd 的正确姿势与收集答案

4.1 矩阵操作细节与常数优化

Floyd 的核心思想是枚举中转点 t，尝试用 dist[i][t] + dist[t][j] 去松弛 dist[i][j]。标准写法就是三层循环，t 在最外层。为什么要 t 在最外层？因为这样才能保证你在处理中转点的时候，所有只使用前 t 个点的最短路都已经被算出来了。这个顺序不能乱，否则 Floyd 会退化成错误结果。

在这个题里 V 很小，最大 800，三层循环最坏是 800^3 = 5.12e8 次操作。纯理论上是能跑完的，但为了稳妥，我会加两个小优化：

第一，在内层循环里跳过 INF。如果 dist[i][t] 是 INF，说明当前 i 和 t 不连通，再往下算没意义；dist[t][j] 同理。这个剪枝对稀疏图效果明显，因为我们的子图最多只有 k 条边，远小于满图，大部分 dist 都是 INF。

第二，利用无向图的对称性，只更新上三角。Floyd 在无向图上每一步都可以保持矩阵对称，所以只需要算 j 从 i+1 到 V-1，松弛成功时同时更新 dist[i][j] 和 dist[j][i]。这样操作次数直接减半。

完整代码如下：

for (int t = 0; t < V; t++) { for (int i = 0; i < V; i++) { if (dist[i][t] == INF) continue; for (int j = i + 1; j < V; j++) { if (dist[t][j] == INF) continue; long long nd = dist[i][t] + dist[t][j]; if (nd < dist[i][j]) { dist[i][j] = dist[j][i] = nd; } } } }

注意这里要求每一对的无向距离都保持对称，所以写入时同时写两边。实测下来这个版本比完整三层循环快不少，而且正确性有保障。

4.2 排序取第 k 个与 INF 过滤

Floyd 跑完之后，dist 矩阵里存的是所有点对之间的最短路径长度。接下来把所有 i < j 的距离收集到一起，排序，直接取下标 k-1 就是答案。

为什么只取 i < j？因为无向图的路径从 u 到 v 和从 v 到 u 是同一条，长度一样，没必要重复统计。为什么要过滤 INF？两个点如果在保留边的子图里不连通，dist 就是 INF，它不应该参与候选排序。虽然 INF 很大，排到最后也不影响前 k 个，但万一候选数量小于 k，输出 INF 会变成野值，还是过滤掉干净。

vector<long long> all; for (int i = 0; i < V; i++) { for (int j = i + 1; j < V; j++) { if (dist[i][j] < INF) { all.push_back(dist[i][j]); } } } sort(all.begin(), all.end()); cout << all[k - 1] << '\n';

这里有个小问题：如果 all.size() 小于 k 怎么办？题目保证第 k 短路径存在，所以理论上不会发生。但为了程序健壮性，可以先判断一下，防御式编程：if (all.size() < k) 输出 -1 或者直接跳过。CF 原题里不会出现这种情况，但本地调试时加上这个判断能帮你快速发现问题。

4.3 复杂度核算

整道题的复杂度分成四块：

• 边排序：O(m log m)，m 最大 2e5，轻松搞定。
• 离散化：O(m log m)，主要是端点排序去重。
• Floyd：O(V^3)，V 最大 2k = 800，理论最坏 5.12e8 次松弛。但子图通常很稀疏，加上 INF 剪枝和对称性优化，实际运行次数远小于这个值。
• 收集排序：O(V^2 log V)，V ≤ 800，几乎可以忽略。

对比一下另一种思路：保留前 k 条边之后，对每个点跑 Dijkstra，复杂度是 O(V * (E log V))，E 最多 k = 400，所以大约 800 * 400 * log800 ≈ 3e6，确实比 Floyd 快一个数量级。但 Floyd 代码更短，理解起来更直接，而且在 CF 的 2 秒时限下也能稳稳通过。如果是大型比赛且时限特别紧，我会优先选 Dijkstra；如果只是想快速 AC，Floyd 足够。

5. 回顾与实测：一些容易 WA 的边角情况

5.1 V=2k时的Floyd性能实测

我实际造过一组极限数据：k = 400，正好保留 400 条边，边分布得比较散，最终离散化出 800 个点。这个子图非常稀疏，完整三层 Floyd 在本地跑大概 1 秒出头；加上跳过 INF 的剪枝后，降到 0.4~0.6 秒；再配合上三角对称优化，一眨眼就跑完了。所以不用担心 Floyd 会超时，关键是别把 INF 当普通数字硬加。

还有个小经验：代码里如果把 INF 设为 4e18，两个 INF 相加会超过 9e18 吗？不会，4e18 + 4e18 = 8e18，仍然小于 long long 的最大值 9.22e18，所以不会溢出。但如果你手滑写成 LLONG_MAX，两个相加直接变成负数，后续比较全部出问题。这个坑我踩过一次，排查了半天才发现是 INF 设置不合理。

5.2 重边、同权、孤立点的处理

重边：初始化 dist 时取 min，这个前面已经写过。如果不管重边直接覆盖，可能会把更短的那条边丢掉，Floyd 算出的最短路偏大。

同权边：直接用前 k 条边大多数时候没问题，但如果想做到无懈可击，可以把所有权值 ≤ 第 k 小边权的边都选进来。这两种策略我都试过，CF 数据下结果一致。个人建议初学者先写简单的“直接取前 k 条”，把主逻辑跑通后再考虑要不要严格化。

孤立点：保留边之外的顶点根本不会出现在 id 映射里，矩阵里也没有它们的位置，所以完全不用处理。这也是离散化的好处：原图再大，和我们相关的只有那几百个点。

INF 过滤：收集答案时一定要跳过 INF。我见过有人把所有 dist[i][j] 直接丢进数组排序，包括 INF。因为 INF 是 4e18，排序后它会排在最后面，只要候选数足够多，对前 k 个确实没影响。但万一这个图本身不连通，候选数不足，输出 INF 就会导致 WA。防御性写法多一行 if，值得加。

5.3 编码习惯与调试建议

最后给几个我总结出的编码习惯，照着写能省不少调试时间。

第一，id 数组一定要初始化为 -1。如果某个原编号没有映射到新编号，后面访问 id[u] 会得到 -1，作为数组下标直接越界。初始化成 -1 后，至少能在调试时一眼看出问题。

第二，排序去重后的 pts 长度 V 才是矩阵大小，不要偷懒直接用 keep 或者 k。k 是边数，V 是点数，两者不相等。我见过有人把循环边界写成 k，结果矩阵越界跑飞了。

第三，收集答案时下标是 k-1，不是 k。vector 从 0 开始，第 k 个元素的下标是 k-1。这个低级错误在比赛中很常见，提交前先拿样例试一次。

第四，调试时可以写一个暴力枚举的小程序，在点数很少的图上把真实第 k 短路径算出来，和 Floyd 结果对比。例如下面这个简单例子：

边：1-2(5), 2-3(1), 3-4(2), 1-3(10) k = 3

保留前 3 条边是 2-3(1)、3-4(2)、1-2(5)，离散化后 4 个点。Floyd 得到所有点对最短路：1 到 2 是 5，1 到 3 是 6，1 到 4 是 7，2 到 3 是 1，2 到 4 是 3，3 到 4 是 2。排序后是 1、2、3、5、6、7，第 3 个是 3。手工验证一下全局路径：最短是 2-3 = 1，第二是 3-4 = 2，第三是 2-3-4 = 3，答案对上了。

我在实际做这类“答案规模比图规模小很多”的题时，最深的体会是：不要被 2e5 吓到，k 小就是告诉你答案只跟很小的一部分数据有关。这道题把取边、离散化、Floyd 三件事串起来，每一环都不难，难的是你敢不敢往“只取前 k 条边”这个方向想。下次再看到 k ≤ 400、图很大的最短路问题，第一反应先问自己：答案会不会只依赖排序后的前 k 个元素？这个思路比背模板值钱得多。