给定一个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
题目大意：
给出一个图，最多能走 k 条边，询问是否能到达 n 点， 如果可以到达则输出最短距离，如果不能到达则输出 “impossible” 。
解题思路：
既然存在负权边，则两种dijkstra都不能用了，考虑bellm - ford 和 spfa，但这道题有边数限制，只能走不超过 k 条边，询问能否到达n点，只能用bellm - ford 了。先看下bellm - ford 的核心算法
for (int i = 0; i < n; i ++){for (int j = 1; j <= m; j ++){int a = e[j].a, b = e[j].b, w = e[j].w;dis[b] = min(dis[b], dis[a] + w);}}
我们发现有内外两重循环，从作用上来看，外循环是走n条边（其实最多走n - 1 条边就够了，因为n 个点，最远n - 1条边），内循环则是枚举所有边进行松弛，既然只能走 k 次，那么改一下外循环，改成
for (int i = 0; i < k; i++)
即可，因为我们最多走k条边，即最多走n 条边，所以改外循环就可以，内循环也要稍加修改，这里要借助一个存档数组backup，存dis上一次的状态，每次用上一次的状态去更新，如果不借助backup则会串联，举个例子：
- 1 2 1
- 2 3 1
- 1 3 4
n = 3, k = 1，很好想，最后dis[n] 应该是 4 ，但是如果不借助backup数组存档，在第一次跑内循环的时候 dis[2] = min(dis[2], dis[1] + 1) = 1 这里是正确的，再往下走，dis[3] = min(dis[3], dis[2] + 1) = 2，这里就出错了，因为只能走一条边，这里却走了两条，所以我们应该用上一次 dis 的状态去更新，借助一个 backup 数组即可。
Code:
#include <iostream>
#include <cstring>using namespace std;const int N = 1e4 + 50;int n, m, k;
int dis[N], backup[N];struct edge { int a, b, w; } e[N];void bellman()
{memset(dis, 0x3f, sizeof dis);dis[1] = 0;for (int i = 0; i < k; i ++)//最多经过 k 条边{memcpy(backup, dis, sizeof dis);//每次用上一次的状态去更新for (int j = 1; j <= m; j ++){int a = e[j].a, b = e[j].b, w = e[j].w;dis[b] = min(dis[b], backup[a] + w);}}
}int main()
{cin >> n >> m >> k;for (int i = 1; i <= m; i ++)cin >> e[i].a >> e[i].b >> e[i].w;bellman();if (dis[n] > 0x3f3f3f3f / 2) puts("impossible");else cout << dis[n] << endl;return 0;
}