AcWing 345 牛站 【BellmanFord算法，非正解】
题目传送门
- \(Bellman-Ford\)算法求解经过不超过\(k\)条边的最短路
- \(Bellman-Ford\)算法求解经过恰好\(k\)条边的最短路（可以重复经过）
前人的足迹,推荐阅读
一、解法I
#pragma GCC optimize(2) //累了就吸点氧吧~
#include
using namespace std;
int id[1010];
const int N = 210;
const int M = 1000010;
int d[N], backup[N];
struct Edge {
int a, b, c;
} edges[M];
int n, k, m, S, E;
int bellmanFord() {
memset(d, 0x3f, sizeof(d));
d[S] = 0;
for (int i = 0; i < k; i++) {
memcpy(backup, d, sizeof(d));
//与最多经过k条边这里不同！
memset(d, 0x3f, sizeof(d));
for (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);
}
}
return d[E];
}
int main() {
cin >> k >> m >> S >> E;
//开始节点为1号
if (!id[S]) id[S] = ++n;
//结束结点为2号,为了防止起点和终点是一个，采用了判断的办法
if (!id[E]) id[E] = ++n;
//修改原来S和E的离散化后的值
S = id[S], E = id[E];
// m条边
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> c >> a >> b;
if (!id[a]) id[a] = ++n;
if (!id[b]) id[b] = ++n;
edges[i].a = id[a], edges[i].b = id[b], edges[i].c = c;
}
//上面的离散化简直太牛B了！
printf("%d", bellmanFord());
return 0;
}
二、解法II
#pragma GCC optimize(2) //累了就吸点氧吧~
#include
using namespace std;
const int N = 205, M = 105;
//现在看来，这个代码写的好垃圾啊，离散化用的不好。代码长
//而且，在用旧的号码记录到邻接表中，然后再去修改，逻辑太长，垃圾！
//相对于另外两套代码，都是在使用hashTable或者unordered_map进行映射后
//再放入邻接表(邻接矩阵)，就方便多了~
int m; //图的边数
int k; //恰好是k条边
int s, t; //起点和终点
struct Edge {
int a; //起点
int b; //终点
int w; //边长
} edges[M];
int p[N]; //使用了哪些点，为了照顾后面的离散化，肯定要尽可能的把点都存储起来，
int tot;
int dist[N], backup[N];
//通过STL将原来的x找到现在新的下标位置
int get(int x) {
return lower_bound(p, p + tot, x) - p;
}
int bellmanFord() {
//最多经过 k 条边：在循环外初始化一次
//恰好经过 k 条边：除在循环外初始化一次外
//还需要在第一层循环中memcpy(backup)后面再次初始化
memset(dist, 0x3f, sizeof dist);
dist[s] = 0; //出发点
for (int i = 0; i < k; i++) {
// 恰好是k条边，迭代k次
/*
1、memset可以理解为是数组有多大，就执行多少次(实际性能比这个强，可以这样估算)
2、其实就算不离散化，直接上来就BellmanFord也是可以的，就是会TLE
3、为什么会TLE呢？因为n最大是1000,点数最大是1e6,那么将面对1000*1e6=1e9的时长
，C++1秒过不了。
4、观察到点数虽多，但边数少，只有100条。满打满算边两头的端点都不一样的话，最多
也就200个点。
5、也就是说很多点没有边连着，是没用的，可以考虑去掉这些无用的点，保留有边的点。
6、去的办法就是离散化，枚举边，找出边的两个端点，然后对端点集合进行离散化。
7、离散化后，需要修改原来点与点之间的关联关系，比如原来是1000，2000这两个点之间
有一条长度为100的边，现在1000映射成了1号点，2000映射成了2号点，需要修改为1到2有
一条长度为100的边才对。
8、我们需对点进行离散化，所以需要把点放到一个数组中，在本代码中就是p数组，
point的意思。这里使用的存储图的方式为按点+边存储方式，所有点存储在p数组中，
所有边存储在e数组中，每一条边包含三个信息：起点，终点，长度。
这样存储的办法，使得我们可以离散化掉无用的点。
BellmanFord算法的存图方式比较牛X(yxc大佬原话)，用一个结构体Edge(u,v,w),
然后开一个数组就行了，随便存，与之前学习的邻接表不同。
原因很简单：因为BellmanFord需要遍历每一条边，怎么能快速遍历每一条边就是关键。
我们以前学习过的邻接表，是按点做索引的，然后记录这个点出发到达哪些点。
如果采用邻接表，就需要枚举每个点，然后二次循环找出每条边，就麻烦了，不如直接
以边为索引来的快了。
9、本题还有一个重要问题:bellmon-ford 算法解决的问题是最多经过k条边的最短路，
而题目问的是恰好经过k条边的最短路径，怎么解决呢？
答：bellmon-ford 每次强制转移即可，即把新的数组赋值为正无穷。
这样每迭代一次数组中i代表的一定是恰好走k步的步数。
这么做的原理是什么呢？什么地方讲过这个原理呢？是现想出来的吗？不可能吧~
*/
// 每次在处理dist数组前备份一下到backup数组
// 只用上一次的迭代结果，就不会发生串联了。
// 上一次的迭代结果可以理解为在上一次x条边限定的情况下的意思
// https://www.acwing.com/video/285/
// 第18分钟讲到了关于串联的问题
memcpy(backup, dist, sizeof dist);
memset(dist, 0x3f, sizeof dist);
for (int j = 1; j <= m; j++) { //枚举m条边
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
dist[b] = min(dist[b], backup[a] + w);
dist[a] = min(dist[a], backup[b] + w);
}
}
//计算在n条限定下的最短距离
return dist[t];
}
int main() {
cin >> k >> m >> s >> t;
for (int i = 1; i <= m; i++) {
int a, b, w;
//一条边的边长以及构成边的两个点的编号
cin >> w >> a >> b;
edges[i] = {a, b, w};
//记录有哪些点，准备离散化去重
p[tot++] = a, p[tot++] = b;
}
//离散化
sort(p, p + tot);
tot = unique(p, p + tot) - p;
//枚举每条边，将第i条边的起点和终点转化为离散化后的新序号
for (int i = 1; i <= m; i++)
edges[i].a = get(edges[i].a), edges[i].b = get(edges[i].b);
//将起点和终点也转化为离散化后的新点号
s = get(s), t = get(t);
//调用bellmanFord算法
printf("%d\n", bellmanFord());
return 0;
}