K-th Path - 题解

比赛与标签

比赛: Codeforces Round 575 (Div. 3) 标签: brute force, constructive algorithms, shortest paths, sortings 难度: *2200

喵喵，这是个什么问题呀？

主人，你好喵~ 今天我们来解决一个超级有趣的寻路问题呐！(ฅ'ω'ฅ)

题目给了我们一张大大的地图（一个连通的无向带权图），上面有 n 个城市（顶点）和 m 条双向道路（边），每条道路都有一个长度（权重）。

我们的任务是，找出所有不同城市对之间（比如从城市A到城市B）的最短旅行时间。然后，把所有这些最短时间从小到大排成一排，找到第 k 小的那个时间是多少。

要注意哦，从城市 A 到城市 B 的最短路和从 B 到 A 是一样的，我们只算一次，而且自己到自己的路程不算在内哦！

寻找第k短路的小秘密喵~

哇，这个图好大呀，有 n 个点呢！如果让我们把所有 n * (n-1) / 2 个点对之间的最短路都算出来，那可太慢了喵... 比如对每个点都跑一次 Dijkstra，复杂度是 O(n * (m + n log n))，肯定会超时的说！(；´Д｀)

但是但是！主人请看，k 的值非常非常小哦，最多只有400！这一定是解题的关键所在，喵~

既然我们只关心前 k 个最短的路径，那这些路径本身应该也不会太长吧？一条很长的路径，怎么可能排到前面去呢？而路径的长度，是由构成它的边的长度累加起来的。所以，我们可以大胆地猜测一下：构成前 k 条最短路径的那些路径，很可能只用到了整个图中边权最小的那一部分边！

这个想法是不是很棒？就像做蛋糕只需要最好的那几颗草莓，而不是把一整个果园的草莓都搬过来一样！

于是，我们的策略就清晰起来啦：

1. 筛选关键边: 我们不需要考虑所有的 m 条边。我们只关心那些权重最小的边。取多少条呢？既然要找第 k 短路，那么就先看看前 k 短的边吧！我们把所有边按权重从小到大排序，只取出前 k 条。

2. 构建核心子图: 这 k 条边连接了多少个点呢？一条边连接2个点，所以最多也就 2*k 个点嘛。当 k=400 时，最多也就800个点。哇，和原来最多 200000 个点相比，这个规模小太多啦！我们就用这 k 条边和它们连接的所有点，构建一个新的、小小的图。

3. 在子图上求解: 在这个小图上，点的数量很少（我们记作 R，R <= 2k），我们就可以放心大胆地计算所有点对之间的最短路了！最简单的方法就是，对小图里的每个点都跑一次 Dijkstra 算法，得到它到其他所有点的最短距离。

4. 收集与排序: 我们把在小图上算出来的所有不同的最短路径长度（d(i, j) 且 i < j）都收集到一个列表里。

5. 找到答案: 最后，把这个列表排序，取出第 k 个元素，就是我们想要的答案啦！因为我们用前 k 条边生成了不止 k 条路径（这些边可以组合嘛），所以第 k 小的路径有极大概率就在其中。事实证明，这个贪心的想法是正确的喵！

让代码动起来喵！

下面就是把这个思路变成现实的代码啦，我已经加上了详细的注释，方便主人理解每一步在做什么哦~

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    // 加速输入输出，让程序跑得更快喵~
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;

    // 用一个元组(tuple)的vector来存储所有的边
    // 格式是 {权重, 点1, 点2}，这样可以直接按权重排序
    vector<tuple<ll, int, int>> edges;
    for (int i = 0; i < m; i++) {
        int x, y;
        ll w;
        cin >> x >> y >> w;
        edges.emplace_back(w, x, y);
    }

    // 第一步：按照边的权重从小到大排序！
    sort(edges.begin(), edges.end());

    // 我们最多只需要考虑前k条边就足够了
    // 如果总边数m比k还小，那就全都要~
    int take = min(m, k);

    // 用一个set来收集这'take'条边所连接的所有点，set可以自动去重哦
    set<int> distinctNodes;
    // Eprime是我们的核心子图的边集
    vector<tuple<ll, int, int>> Eprime; 
    for (int i = 0; i < take; i++) {
        auto [w, u, v] = edges[i];
        distinctNodes.insert(u);
        distinctNodes.insert(v);
        Eprime.emplace_back(w, u, v);
    }

    // 把set里的不连续的节点编号，映射到从0开始的连续新编号
    vector<int> nodes(distinctNodes.begin(), distinctNodes.end());
    int R = nodes.size(); // R 是我们子图的节点数
    map<int, int> node_to_index;
    for (int i = 0; i < R; i++) {
        node_to_index[nodes[i]] = i;
    }

    // 这就是我们构建的只包含关键点的小图啦！
    vector<vector<pair<int, ll>>> graph(R);
    for (auto [w, u, v] : Eprime) {
        int i = node_to_index[u];
        int j = node_to_index[v];
        graph[i].emplace_back(j, w);
        graph[j].emplace_back(i, w);
    }

    // 存放所有计算出的最短路径长度
    vector<ll> all_dists;
    // 对小图里的每一个点，我们都跑一次Dijkstra算法
    for (int i = 0; i < R; i++) {
        vector<ll> dist(R, LLONG_MAX); // 初始化距离为无穷大
        // 优先队列优化的Dijkstra
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
        
        dist[i] = 0;
        pq.emplace(0, i);

        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();

            if (d != dist[u]) continue; // 已经有更短的路径了，跳过

            for (auto [v, w] : graph[u]) {
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.emplace(dist[v], v);
                }
            }
        }
        
        // 把从i出发到其他点的最短路存起来 (j > i 保证不重复)
        for (int j = i + 1; j < R; j++) {
            if (dist[j] != LLONG_MAX) {
                all_dists.push_back(dist[j]);
            }
        }
    }

    // 最后一步，排序所有找到的路径长度
    sort(all_dists.begin(), all_dists.end());

    // 输出第k个！因为数组下标从0开始，所以是k-1的位置
    if (k <= all_dists.size()) {
        cout << all_dists[k - 1] << endl;
    } else {
        // 如果生成的路径总数小于k，题目保证k不会超过总路径数，
        // 但为了代码健壮性，这里可以输出最后一个
        cout << all_dists.back() << endl;
    }

    return 0;
}

跑得快不快呀？

• 时间复杂度: O(m log m + k² log k) 的说

  • 对 m 条边排序需要 O(m log m)。
  • 构建子图需要 O(k)。
  • 子图的节点数 R 最多为 2k，边数最多为 k。
  • 我们对子图中的 R 个节点，每个都跑了一次 Dijkstra。Dijkstra 的复杂度是 O(E' + R log R)，其中 E' 是子图边数。所以这部分总共是 O(R * (k + R log R))。代入 R = O(k)，就是 O(k * (k + k log k)) = O(k² log k)。
  • 最后对所有找到的路径排序，路径数量最多是 O(R²) = O(k²) 条，排序需要 O(k² log(k²)) = O(k² log k)。
  • 所以总的复杂度由 O(m log m) 和 O(k² log k) 决定。因为 m 可能很大，所以主要是排序边的时间开销，后面处理小图的部分因为 k 很小，所以非常快！

• 空间复杂度: O(m + k²) 的说

  • 存储所有 m 条边需要 O(m) 的空间。
  • 子图的邻接表需要 O(R + E') = O(k) 的空间。
  • 存储所有找到的最短路径需要 O(R²) = O(k²) 的空间。
  • 所以总的空间复杂度是 O(m + k²)，也是很够用的说！

这次学到了什么喵？

主人，这次的冒险是不是超有收获？我们来总结一下学到的小知识点吧！

1. 核心思想 - 降维打击: 这道题最精髓的地方就是观察到 k 很小，从而把一个在大图上看似无解的 All-Pairs Shortest Path 问题，转化成了一个在关键点构成的子图上的可解问题！这是一种非常重要的、通过抓住问题瓶颈来简化问题的思想，喵~

2. 贪心选择: 我们贪心地只选择权重最小的 k 条边来构建子图，这个策略非常有效。它告诉我们，最终的解往往隐藏在最优的局部结构中。

3. Dijkstra算法的应用: Dijkstra 是求单源最短路径的经典算法，一定要熟练掌握哦！在这里，我们通过对子图的每个点都跑一次 Dijkstra，巧妙地解决了子图上的 All-Pairs Shortest Path 问题。

4. 离散化/节点映射: 当题目给的点编号很大但不连续时（比如 1, 5, 1000），将它们映射到 0, 1, 2... 这样的连续整数，是处理图论问题的常用技巧。它能让数组和邻接表的使用变得非常方便和高效，喵~

所以呀，主人~ 以后遇到看起来很吓人的大数据问题，一定要仔细看看有没有什么特殊的、小小的约束条件，那可能就是解题的突破口哦！加油喵！(๑•̀ㅂ•́)و✧