CF1196F K-th Path 题解 floyd

题目链接：https://codeforces.com/problemset/problem/1196/F

题目大意：

给定一个包含 \(n\) 个节点 \(m\) 条边的无向图（\(n,m \le 2 \cdot 10^5\)）。

图中任意两点之间（如果连通的话）都存在一条最短路（节点 \(i\) 到它自己不算最短路，\(i\) 到 \(j\) 的最短路 和 \(j\) 到 \(i\) 的最短路视为同一条）。

求：第 \(k\) 小的最短路（\(1 \le k \le 400\)）。

解题思路：

如果将 \(m\) 条边按照长度从小到大排，可以发现解决这个问题（求第 \(k\) 小的最短路长度）最多只需要用到最短的 \(\min(k, m)\) 条边。

然后你可以保留最短的 \(\min(k, m)\) 条边，删去剩余的边，然后你会发现最多只剩下 \(2 \min(k, m)\) 的节点是有边连接的 —— 最短路肯定也只包含这些节点。

然后你可以选出这些点然后用 floyd 算法求最短路。

时间复杂度 \(O(m \log m + k^3)\)。

示例程序：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 810, maxm = 2e5 + 5;
struct Edge {
    int u, v, w;

    bool operator < (const Edge &b) const {
        return w < b.w;
    }
} edge[maxm];
int n, m, k, len;
long long dis[maxn][maxn];

int main() {
    scanf("%d%d%d", &n, &m, &k);
    len = min(k, m);
    for (int i = 0; i < m; i++)
        scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
    sort(edge, edge+m);
    vector<int> vec;
    for (int i = 0; i < len; i++) {
        vec.push_back(edge[i].u);
        vec.push_back(edge[i].v);
    }
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    n = vec.size();
    memset(dis, 0x3f, sizeof(dis));
    for (int i = 1; i <= n; i++) dis[i][i] = 0;
    for (int i = 0; i < len; i++) {
        int x = lower_bound(vec.begin(), vec.end(), edge[i].u) - vec.begin() + 1;
        int y = lower_bound(vec.begin(), vec.end(), edge[i].v) - vec.begin() + 1;
        dis[x][y] = dis[y][x] = edge[i].w;
    }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
    vector<long long> ans;
    for (int i = 1; i < n; i++)
        for (int j = i+1; j <= n; j++)
            if (dis[i][j] < 1e15)
                ans.push_back(dis[i][j]);
    sort(ans.begin(), ans.end());
    printf("%lld\n", ans[k-1]);
    return 0;
}