Bellman-Ford算法

适用范围：处理权值带负数的，且有边数限制的最短路问题

---

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。

注意：图中可能 存在负权回路 。

输入格式
第一行包含三个整数 n,m,k。

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

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

如果不存在满足条件的路径，则输出 impossible。

数据范围
1≤n,k≤500,
1≤m≤10000,
任意边长的绝对值不超过 10000。

输入样例：
3 3 1
1 2 1
2 3 1
1 3 3
输出样例：
3

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

const int N = 10050;
int n, m, k;
int a[N][N], d[N], t[N];	//d为到1号的距离，t为d的备份

struct Edge		//a b c 分别为 从a到b的一条边权值为w
{
    int a, b, w;
}edge[N];	

int bellmanFord()
{
    memset(d, 0x3f3f3f3f, sizeof(d));	//初始化d
    d[1] = 0;							//初始化
    for (int i = 1; i <= k; i++)		//遍历限制数k
    {
        memcpy(t, d, sizeof(d));		//备份d
        for (int j = 1; j <= m; j++)	//遍历每条边
        {
            int a = edge[j].a;
            int b = edge[j].b;
            int w = edge[j].w;
            d[b] = min(d[b], t[a] + w);		//更新d
        }
    }
    return d[n];
};

int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        edge[i] = { x,y,z };
    }

    if (bellmanFord() > 0x3f3f3f / 2) cout << "impossible" << endl;
    else cout << bellmanFord() << endl;
}

Q.E.D.