有额外限制的 bellman_ford 算法

题目链接

1.有限制的 $Bellman\_Ford$

时间复杂度: $O(N\ast M)$

在传统的 $Bellman\_Ford$ 中，可以处理边数不大于 $K$ 条边的最短距离
但我们只要加一条限制(实际上只多了两行代码)
就可以实现求恰好等于 $K$ 条边的最短距离
具体的就在于其核心代码中:

 for(int i = 0; i < k; i ++ )    //最大经过几条边就迭代几次{           memcpy(backup, dist, sizeof dist);for(int j = 0; j < m; j ++ )    //遍历所有边更新最短路{int a = edge[j].a, b = edge[j].b, w = edge[j].w;dist[b] = min(dist[b], backup[a] + w);  //每次更新到顶点b的边}}

其中为什么要拷贝一份 $dist$ 数组就不解释了
我们只要将上述代码改为:

    for (int i = 0; i < k; i++) {memcpy(backup, d, sizeof(d));//与最多经过k条边这里不同！memset(d, 0x3f, sizeof(d)); //addfor (int j = 0; j < m; j++) {int a = edges[j].a, b = edges[j].b, c = edges[j].c;//与最多经过k条边这里不同！d[b] = min(d[b], backup[a] + c);d[a] = min(d[a], backup[b] + c);//add，可以与上面的交换位置}}

最大的不同在于我们拷贝完 $dist$ 数组之后，反手将 $dist$ 数组初始化为正无穷了
这样在下一次松弛操作的时候，我们就必须进行松弛了，因为任何数肯定小于这个正无穷
只不过在松弛的时候，不仅要松弛 $dsit[b]$，还要松弛 $dist[a]$
注意经过的边虽然满足恰好 $K$ 条，但是可能会有重复的边！

#pragma GCC optimize(2) //累了就吸点氧吧~#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>using namespace std;const int N = 210, M = 1000010;int n, m, st, en, k;
int dist[N], backup[N];
unordered_map<int, int> id;
struct Edge{//Bellman_Ford的数据结构为三元组int a, b, c;
}edge[M];int Bellman_Ford()
{memset(dist, 0x3f, sizeof dist);dist[id[st]] = 0;for(int i = 0; i < k; i ++ ){memcpy(backup, dist, sizeof dist);//是在外层循环copy的!!!memset(dist, 0x3f, sizeof dist);for(int j = 0; j < m; j ++ ){int a = edge[j].a, b = edge[j].b, c = edge[j].c;dist[b] = min(dist[b], backup[a] + c);dist[a] = min(dist[a], backup[b] + c);}}return dist[id[en]];
}int main()
{cin >> k >> m >> st >> en;if(!id.count(st))   id[st] = ++ n;if(!id.count(en))   id[en] = ++ n;for(int i = 0; i < m; i ++ ){int a, b, c;cin >> c >> a >> b;//这道题比较恶心,需要先读入边长if(!id.count(a)) id[a] = ++ n;if(!id.count(b)) id[b] = ++ n;edge[i] = {id[a], id[b], c};}// cout << n << endl;// for(int i = 1; i <= n; i ++ )   cout << dist[i] << " \n"[i == n];cout << Bellman_Ford() << endl; return 0;
}

---

2.倍增思想Floyd

参考：
1
2
3