$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

Bellman-Ford 算法：
有点S*的算法

1. 循环 $n$ 次。
2. 每层循环循环每条边，使用三角不等式进行松弛操作。
3. 可以处理负权边，判断负环。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 510, M = 1e4 + 10;
int n, m, k;
int dist[N], back[N];
struct Edge {
    int a, b, c;
} edge[M];

int bellman_ford() {
    dist[1] = 0;
    for (int i = 1; i <= k; i++) {
        memcpy(back, dist, sizeof dist);
        for (int j = 1; j <= m; j++) {
            int a = edge[j].a, b = edge[j].b, w = edge[j].c;
            dist[b] = min(dist[b], back[a] + w);
        }
    }
    if (dist[n] >= 0x3f3f3f3f / 2) return -0x3f3f3f3f;
    return dist[n];
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= m; i++) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        edge[i] = {u, v, w};
    }
    memset(dist, 0x3f3f3f3f, sizeof dist);
    int ans = bellman_ford();
    if (ans == -0x3f3f3f3f) puts("impossible");
    else printf("%d", ans);
    return 0;
}