Bellman-Ford 算法

算法原理
    第一个循环n次 （第x次表示从一号点，经过不超过x条边的最短路的距离）
        （在acwing853题中，这里备份一下，只用上一次的迭代结果，避免出现连锁修改。
（可举例））
        第二个循环遍历所有边
            更新最短距离（类似djikstra）

可以使用结构体存储。
用于处理有负权边的。
注意：不能处理负权回路，会无限循环。当第一个循环在第n次的时候仍然在更新，
说明有负权回路，因为最短路经过的边数超过了n条边。

//acwing 853
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 510, M = 10010;

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

struct Edge
{
	int a, b, w;
}edges[M];

int bellman_ford()
{
	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, b = edges[j].b, w = edges[j].w;
			dist[b] = min(dist[b], backup[a] + w);

		}
	}
	if (dist[n] > 0x3f3f3f3f / 2) return -1;
	return dist[n];
}

int main()
{
	scanf("%d%d%d", &n, &m, &k);

	for (int i = 0; i < m; i++)
	{
		int a, b, w;
		scanf("%d%d%d", &a, &b, &w);
		edges[i] = { a,b,w };
	}
	int  t = bellman_ford();

	if (t == -1) puts("impossible");
	else printf("%d\n", t);

}