题目入口
题意：给定一个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
思路：
原理：和Dijkstra的原理有些相似。
- 迭代n次，每次循环遍历m条边(a -> b = w)，进行松弛操作(dist[b] = min(dist[b], dist[a] + w))，如此最后便可以得到答案
- 注意：在每次迭代的时候需用另一个数组backup复制上一轮迭代的dist结果，然后用backup[a]去更新dist[b]，因为可能出现串联情况就容易出问题。
eg: 样例中 1 -> 2 = 1， 2 -> 3 = 1，1 -> 3 = 3，k=1。
如果我们不复制一遍的话，可能在第一次迭代时先更新了dist[2]=1；但当枚举到2 -> 3的边时如果用新的dist[2]去更新，dist[3]=2并且走了2条边；
但如果我们用backup[2]去更新dist[3]= min(3， 0x3f+1) = 3，只走了1 -> 3这一条边。
用bellman-ford判断负环：
- 当迭代到第n次时还有边被更新，说明存在一条n条边的最短路，但却只有n个点，说明其中有一条边重复了，必定存在负环。
代码实现： O(nm)
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <cstring>
#include <iostream>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#define lowbit(x) (x &(-x))
#define me(ar) memset(ar, 0, sizeof ar)
#define mem(ar,num) memset(ar, num, sizeof ar)
#define rp(i, n) for(int i = 0, i < n; i ++)
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define pre(i, n, a) for(int i = n; i >= a; i --)
#define IOS ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int way[4][2] = {
{
1, 0}, {
-1, 0}, {
0, 1}, {
0, -1}};
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const int INF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0);
const double EXP = 1e-8;
const ll MOD = 1e9 + 7;
const int N = 505, M = 1e5 + 5;int n, m, k;
int dist[N], backup[N];struct node{
int a, b, w;
}edges[M];int bellman_ford()
{
mem(dist, 0x3f);dist[1] = 0;//求的是k条边的最短路就迭代k次for(int i = 0; i < k; i ++){
//每次用backcup复杂上次迭代后的结果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;//得用backcup[a]来更新b点距离dist[b] = min(dist[b], backup[a] + w);}}//可能存在负权边，所以距离可能不再等于0x3f了if(dist[n] > 0x3f3f3f3f / 2) return -1;return dist[n];
}signed main()
{
IOS;cin >> n >> m >> k;for(int i = 0; i < m; i ++){
int a, b, w;cin >> a >> b >> w;edges[i] = {
a, b, w};}int ans = bellman_ford();if(ans == -1) puts("impossible");else cout << ans << endl;return 0;
}