BF 算法解决有边数限制的最短路径

为了防止链式更新, 需要用到一个 backup 数组, 以免 a 更新了 b, 在同一次迭代里 b 又更新了 c 点.
每次迭代都要枚举 m 条边有点笨, 所以 spfa 算法就是为了优化 BF 的, 用邻接表存储边, 每次只更新
d[a] 发生变化了的所有边. 用队列记录记录所有变化了的节点.

BF 算法也可以用来判断负环

迭代第 n 次时, 如果发现还有某个点的距离发生了变化, 那就说明存在一条长度为 n + 1 的路径, 就
必定存在负权回路.

#include <iostream>
#include <cstring>
using namespace std;

const int N = 100010;

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

int n, m, k, x, y, z;
int d[N], backup[N];

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

    for (int i = 1; i <= k; i++) {
        memcpy(backup, d, sizeof(d));   // 防止链式更新, 下面更新 d[b] 时要用到 backup[a] 不能用 d[a]
        for (int j = 0; j < m; j++) {
            int a = edges[j].a, b = edges[j].b, c = edges[j].c;
            d[b] = min(d[b], backup[a] + c);
        }
    }

    return d[n];
}

int main() {
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        cin >> x >> y >> z;
        edges[i].a = x, edges[i].b = y, edges[i].c = z;
    }

    int t = bf();
    if (t > 0x3f3f3f3f / 2) cout << "impossible" << endl;
    else cout << t << endl;
    return 0;
}