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

题目

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;
}