Bellman-Ford算法加一个判断条件避免傻瓜式地毯遍历每条边

看完y总的视频，其中的SPFA算法利用一个队列优化，可以避免傻瓜式地毯遍历每条边；然后我思考了一下，也可以在遍历每条边的同时，用一个flag来判断是否有松弛操作，若遍历完每一条边均为无松弛操作发生，就结束循环！这样也就达到了与SPFA算法相同的效果，可能时间复杂度会偏高一点。

    bool flag = false; //增加一个flag判断是否发生松弛操作
    for (int j = 1; j <= m; j ++){
        int a = edges[j].a, b = edges[j].b, w = edges[j].w;
        if (backup[a] + w < d[b]){
            d[b] = backup[a] + w;
            flag = true; // 发生变为true
        }
    }
    if (!flag) break; //遍历完边之后没有发生松弛操作，结束遍历

完整代码

#include <iostream>
#include <cstring>


using namespace std;
const int N = 100010, M = 100010;
int d[M], backup[M], n, m;

struct Edge{
    int a, b, w;
}edges[N];

int bellmanford(){
    memset(d, 0x3f, sizeof d);
    d[1] = 0;

    for (int i = 0; i < n; i ++){
        memcpy(backup, d, sizeof d);

        bool flag = false;
        for (int j = 1; j <= m; j ++){
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if (backup[a] + w < d[b]){
                d[b] = backup[a] + w;
                flag = true;
            }
        }
        if (!flag) break;
    }

    if (d[n] > 0x3f3f3f3f / 2) return -1;
    return d[n];
}

int main(){
    cin >> n >> m;
    for (int i = 1; i <= m; i ++){
        int a, b, w;
        cin >> a >> b >> w;
        edges[i] = {a, b, w};
    }
    int s = bellmanford();
    if (s == -1) cout << "impossible";
    else cout << s;
    return 0;
}

优化后的代码在 1 ≤ n, m ≤ 10^5 都是可以ac的，将此代码放入SPFA模板中可以ac；此代码的优点主要是兼并了处理最多经过k条边的条件限制，非常好用！