Bellman_ford算法解决负边权与有边数限制的最短路问题模板

题目链接

解决单源最短路问题，存在负边权，时间复杂度 O ( n m ) O(nm) O(nm)

计算最多经过k步，从1到n的最小权重和。

#include
using namespace std;

const int N = 510, M = 10010, INF = 0x3f3f3f3f;

int n, m, k;
int d[N], backup[N];

struct edge {
	int a, b, w;
} e[M]; 

void bellman_ford () {
	
	memset (d, 0x3f, sizeof d); // 注意初始化 
	d[1] = 0;
	
	for (int i = 1;i  n >> m >> k;
	for (int i = 0;i > a >> b >> w;
		e[i] = {a, b, w};
	}
	
	bellman_ford ();
	
	if (d[n] > INF / 2) puts ("impossible"); // 存在负边权，可能会导致INF加上负边权而变小，所以不可以用等于INF来判断。
	else cout