Bellman Ford算法

题目链接：https://www.acwing.com/problem/content/855/

题目描述

给定一个 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

Bellman Ford算法

算法介绍

Dijkstr算法无法解决含有负权边的最短路问题，而Bellman Ford算法可以，并且还可以解决限定边的数目的最短路径的求解。

算法步骤

需要额外注意一点，算法使按照最短路中边的数目递增的顺序计算的，如果在同一轮中，某个dist[i]被更新且后续被使用则会发生错误，因此进行新一轮的计算时应该先备份上一轮的数据，详见代码。

AC代码

---

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 501;
const int M = 1e4 + 10;
int n, m, k;
int dist[N];
int backup[N];

struct edge
{
	int a;
	int b;
	int c;
};
edge edges[M];

int bellman_ford()
{
    /* 注意负权边和0x3f3f3f3f是可以更新dist[i]的
	 * 但其仍然是不可达的
	 * 因此最后注意对这一情况的处理*/
	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 a = edges[j].a;
			int b = edges[j].b;
			int c = edges[j].c;
			dist[b] = min(dist[b], backup[a] + c);  //就是这
		}
	}

	return dist[n];
}

int main()
{
	cin >> n >> m >> k;
	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		edges[i] = {a, b, c};
	}
	int res = bellman_ford();
    /* 负权边的存在，可能会让d[a][b]小于INF
	 * 且图中边的长度小于10000
	 * 因此用0x3f3f3f3f/2来处理这种情况即可 */
	if (res >= 0x3f3f3f3f / 2)
		cout << "impossible" << endl;
	else
		cout << res << endl;
	return 0;
}