Bellman_ford

时间复杂度 = O(mn)

• 主要思想：循环k次，每一次都对每一条边进行松弛
• 主要应用：可以解决负权边存在的情况
• 存图方式：都可以
• backup的存在是为了保证每一次更新都是采用的上一次的更新结果（第一重循环是k条边）
• 最后与inf / 2作比较，是因为有可能上一次的更新点结果是inf，但是他们之间是可达到的，虽然我们主观认为无穷+-一个数依然是无穷，但在计算机系统中他就是改变了，所以要与inf/2作比较
• 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e6 + 10, inf = 0x3f3f3f3f3f3f3f3f3f;
ll n, m, k, dist[N], backup[N];

struct edge {
    ll u, v, w;
}edges[N];

ll bellman_ford() {
    memset(dist, inf, sizeof dist);
    dist[1] = 0;
    for(int i = 1; i <= k; i++) {
        memcpy(backup, dist, sizeof dist);
        for(int j = 1; j <= m; j++) dist[edges[j].v] = min(dist[edges[j].v], backup[edges[j].u] + edges[j].w);
    }
    return dist[n] > inf / 2 ? -1 : dist[n];
}

int main() {
    cin >> n >> m >> k;
    for(int i = 1; i <= m; i++) cin >> edges[i].u >> edges[i].v >> edges[i].w;
    if(bellman_ford() == -1) puts("impossible");
    else cout << bellman_ford() << '\n';
    return 0;
}