bellman_ford算法

应用
1. 若n次迭代时，仍有最短路径被更新，则存在负回路，可用来判断是否存在负权回路

核心思想
1. k次迭代表示经过不超过k条边到达当前节点
2. dist表示当前点到源点的最短距离
3. 边直接用结构体存储即可

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510, M = 100010, INF = 0x3f3f3f3f;
int n, k, m;

struct edge {
    int s, e, v;
} ed[M];

int dist[N], backup[N];

void bellman_ford() {
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;

    for (int i = 0; i < k; i++) {
        memcpy(backup, dist, sizeof(dist));

        for (int j = 0; j < m; j++) {
            int s = ed[j].s, e = ed[j].e, v = ed[j].v;
            dist[e] = min(dist[e], backup[s] + v);
        }
    }

}


int main() {
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        cin >> ed[i].s >> ed[i].e >> ed[i].v;
    }

    bellman_ford();

    if (dist[n] > INF / 2) cout << "impossible" << endl;
    else cout << dist[n] << endl;

    return 0;
}