恰好边数限制的最短路(边的数量很大)

题目

345. 牛站

算法标签: $Bellman-Ford$算法, 倍增算法, 矩阵乘法

思路

注意到, 最短路有边数限制, 直接考虑$Bellman-Ford$算法, 但是这里求得是恰好$k$条边的最短路, 因此每次更新的时候都需要重置转移数组, 并且这样的时间复杂度是$O(nm)$的有可能会超时, 因此需要进行优化, 可以预处理一个状态转移数组$f[i][j][k]$表示从点$i$到$j$经过了$2^k$步的最短路, 这样只需要像快速幂一样将二进制数中的每个$1$取出就能得到答案

$Bellman-Ford$代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 210, M = N * N;

int n, m, s, t;
struct Edge {
    int u, v, w;
} edges[M];
int d[N], tmp[N];
vector<int> desc;

int get(int val) {
    return lower_bound(desc.begin(), desc.end(), val) - desc.begin();
}

void bellman_ford() {
    memset(d, 0x3f, sizeof d);
    d[s] = 0;
    for (int i = 0; i < n; ++i) {
        memcpy(tmp, d, sizeof d);
        memset(d, 0x3f, sizeof d);
        for (int k = 0; k < m; ++k) {
            auto &[u, v, w] = edges[k];
            if (tmp[u] + w < d[v]) d[v] = tmp[u] + w;
            if (tmp[v] + w < d[u]) d[u] = tmp[v] + w;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    cin >> n >> m >> s >> t;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        edges[i] = {u, v, w};
        desc.push_back(u), desc.push_back(v);
    }
    
    sort(desc.begin(), desc.end());
    desc.erase(unique(desc.begin(), desc.end()), desc.begin());
    
    //将点进行离散化
    s = get(s), t = get(t);
    for (int i = 0; i < m; ++i) {
        auto &[u, v, w] = edges[i];
        u = get(u), v = get(v);
    }
    
    bellman_ford();
    
    cout << d[t] << "\n";
    
    return 0;
}

倍增算法代码

算法瓶颈在预处理, 时间复杂度$O(n^3)$

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 210, M = N * N, K = 21;

int n, m, s, t;
struct Edge {
    int u, v, w;
} edges[M];
vector<int> desc;
int f[N][N][K];

int get(int val) {
    return lower_bound(desc.begin(), desc.end(), val) - desc.begin();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m >> s >> t;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        edges[i] = {u, v, w};
        desc.push_back(u), desc.push_back(v);
    }

    sort(desc.begin(), desc.end());
    desc.erase(unique(desc.begin(), desc.end()), desc.begin());

    //将点进行离散化
    s = get(s), t = get(t);
    for (int i = 0; i < m; ++i) {
        auto &[u, v, w] = edges[i];
        u = get(u), v = get(v);
    }
    
    memset(f, 0x3f, sizeof f);
    for (int k = 0; k < K; ++k) {
        for (int i = 0; i < desc.size(); ++i) {
            for (int j = 0; j < desc.size(); ++j) {
                for (int l = 0; l < desc.size(); ++l) {
                    f[i][j][k] = min(f[i][j][k], f[i][l][k - 1] + f[l][j][k - 1]);
                }
            }
        }
    }
    
    int ans[N], tmp[N];
    ans[s] = 0;
    for (int k = 0; k < K; ++k) {
        if (n >> k & 1) {
            memset(tmp, 0x3f, sizeof tmp);
            for (int i = 0; i < desc.size(); ++i) {
                for (int j = 0; j < desc.size(); ++j) {
                    tmp[i] = min(tmp[i], ans[j] + f[j][i][k]);
                }
            }
            memcpy(ans, tmp, sizeof tmp);
        }
    }
    
    cout << ans[t] << "\n";
    return 0;
}