T3-8 K-th Path

思路分析

题意

给定一张 $n$ 个点、$m$ 条边的无向带权图，求所有点对最短路中第 $k$ 小的值。

数据范围的矛盾与突破口

• $n$ 高达 $2 \times 10^5$，做全源最短路（如 Floyd $O(n^3)$）根本不可能
• 但 $k \leq 400$ 非常小——这是突破口

关键推导（为什么只取前 $k$ 条边就够了）

1. 将所有边按权值从小到大排序，记第 $i$ 条边权值为 $w_i$
2. 前 $k$ 条边给出了 $k$ 个不同的点对 $(u_i, v_i)$，每对之间的最短路 $d(u_i, v_i) \leq w_i \leq w_k$
3. 所以至少有 $k$ 个最短路 $\leq w_k$，即第 $k$ 小的最短路 $\leq w_k$
4. 对于任何长度 $\leq w_k$ 的最短路，其路径上的每一条边权值都 $\leq w_k$，而权值 $\leq w_k$ 的边一定在排序后的前 $k$ 条里
5. 因此，前 $k$ 条边已经包含了所有我们关心的最短路需要的全部信息

缩图规模

前 $k$ 条边最多涉及 $2k = 800$ 个节点，对这些节点跑 Floyd 即可：$800^3 \approx 5 \times 10^8$，刚好能过。

算法流程

① 所有边按权值排序
② 取前 k 条边，离散化涉及的节点（≤ 800 个）
③ 建图，跑 Floyd 全源最短路
④ 收集所有点对的距离，排序，输出第 k 个

---

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;               // 边数上限
int n, m, k;                           // n 个点, m 条边, 求第 k 小最短路
struct node {
    int x, y, z;                       // 一条边：端点 x, y，权值 z
} a[N];                                // 存储所有边
bool cmp(node a, node b) {
    return a.z < b.z;                  // 按边权从小到大排序
}
map<int, int> ma;                      // 离散化映射：原始节点编号 → 新编号 1,2,3,...
int f[805][805];                       // Floyd 距离矩阵，805 > 2*400 = 800
int q;                                 // 离散化后的节点总数
int w[805 * 805];                      // 存储所有点对的最短路值
int t;                                 // w 数组的当前长度
int main() {
    ios::sync_with_stdio(false);       // 关闭同步，加速输入输出
    cin.tie(nullptr);
    cin >> n >> m >> k;                // 读入 n, m, k
    for (int i = 1; i <= m; i++)cin >> a[i].x >> a[i].y >> a[i].z;  // 读入每条边
    sort(a + 1, a + 1 + m, cmp);      // 所有边按权值从小到大排序
    memset(f, 0x3f, sizeof(f));        // 距离矩阵初始化为 INF（0x3f3f3f3f ≈ 1.06×10⁹）
                                       // memset 按字节填充 0x3f，int 4 字节 → 0x3f3f3f3f
    // ===== 取前 k 条边，离散化节点并建图 =====
    for (int i = 1; i <= k; i++) {
        // 如果端点 x 第一次出现，分配新编号
        if (ma[a[i].x] == 0) ma[a[i].x] = ++q;
        // 如果端点 y 第一次出现，分配新编号
        if (ma[a[i].y] == 0) ma[a[i].y] = ++q;
        // 用新编号在距离矩阵中记录这条边（无向图，双向赋值）
        f[ma[a[i].x]][ma[a[i].y]] = a[i].z;
        f[ma[a[i].y]][ma[a[i].x]] = a[i].z;
    }
    // 自己到自己的距离为 0
    for (int i = 1; i <= q; i++) f[i][i] = 0;
    // ===== Floyd 全源最短路 =====
    // 三重循环：枚举中转点 p，更新 i→j 的最短路
    // 注意：0x3f3f3f3f + 0x3f3f3f3f = 0x7e7e7e7e < INT_MAX，不会溢出
    for (int p = 1; p <= q; p++)           // 枚举中转点
        for (int i = 1; i <= q; i++)       // 枚举起点
            for (int j = 1; j <= q; j++)   // 枚举终点
                f[i][j] = min(f[i][j], f[i][p] + f[p][j]);  // 松弛操作
    // ===== 收集所有点对最短路 =====
    // i < j 避免 (a,b) 和 (b,a) 重复计数
    // 不过滤 INF：不连通的点对距离极大，排序后自然排到末尾，不影响前 k 个
    for (int i = 1; i <= q; i++)
        for (int j = i + 1; j <= q; j++) {
            t++;                           // 结果数组长度 +1
            w[t] = f[i][j];               // 记录这对点的最短路
        }
    sort(w + 1, w + 1 + t);              // 所有最短路从小到大排序
    cout << w[k] << "\n";                 // 输出第 k 小的值
    return 0;
}