AcWing 853. 有边数限制的最短路
for n次
for 所有a, b, w
dist[b] = min(dist[b], dist[a] + w);（松弛操作）
Bellman-Ford算法证明了循环完之后所有边的距离一定满足
dist[b] <= dist[a] + w（三角不等式）。
当图中存在负权回路时，一般不存在最短路径。
如果负环不在1到n的路径上或存在边数限制，那么就不影响最短路径的求解。
第n - 1次更新的最短路径的边数一定是n - 1，所以第n次如果更新了某条最短路的长度，那么这条最短路上就包含n条边，即包含n + 1个点，由抽屉原理可知，必然存在两个点的编号相同，即必然存在负环（只有负环第n次才会更新）。
#include <cstring>
#include <iostream>
#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];
void bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < k; i ++ ) // 迭代k次后，dist数组表示从1经过不超过k条边到每个点的最短距离
{
memcpy(backup, dist, sizeof dist); // 串联指在一次迭代中更新多条边，备份dist数组是用来解决串联问题的（保证只用上一次迭代的结果）
for (int j = 0; j < m; j ++ )
{
auto e = edges[j];
dist[e.b] = min(dist[e.b], backup[e.a] + e.w); // 这里的backup[e.a] + e.w是解决串联问题的核心，保证每次只更新一条边
}
}
}
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};
}
bellman_ford();
if (dist[n] > 0x3f3f3f3f / 2) puts("impossible"); // 不写dist[n] == 0x3f3f3f3f 是为了避免出现dist[n] = 0x3f3f3f3f - constant的情况
else printf("%d\n", dist[n]);
return 0;
}