bellman_ford算法

特点就是可以求解限制最大数的最短路，并且可以求解带负边最短路，如果不限制边数可以选择使用dijkstra算法，如果有负边可以选择spfa算法。

算法的思想就是存储一下源点到每个点的距离，每循环一次更新一遍这个数据，就可以控制循环次数来限制边数，每次更新就是把所有的边遍历判断一遍，如果可以更新就更新距离。

题目描述

第一行包含三个整数 n,m,k。

接下来 m行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出一个整数，表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。

C++

#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 1e5 + 10;
struct Edge
{
    int a, b ,c;
}edge[maxn];
int n, m, k;
int dist[maxn];
int backup[maxn];
void bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 1; i <= k; i++)
    {
        memcpy(backup, dist, sizeof dist);
        for (int j = 1; j <= m; j++)
        {
            auto t = edge[j];
            int x = t.a, y = t.b, s = t.c;
            dist[y] = min(dist[y], backup[x] + s);
        }
    }
}
int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        edge[i] = {a, b, c};
    }
    bellman_ford();
    if (dist[n] > 0x3f3f3f3f / 2) cout << "impossible" << endl;
    else cout << dist[n] << endl;
    return 0;
}

注意：当一条路径更新过后，这个图还没有遍历完，那么以这条边的终点为起点的数据将会被影响，但是这时边数还不足到这条边，所以要用一个备份的数据去做更新。