存储：
这个算法存边不一定要写成邻接表，随便存，只要能遍历到所有边即可，结构体数组。
过程：
负权边、负权回路：
贝尔曼福特算法处理有负权边的图。(注意，有负权回路的话，最短路径就不一定存在了。)(负权回路，一圈的长度小于0。)
贝尔曼福特算法是可以求出是否存在负权回路的。(但一般找负环不用他来做，用spfa，因为贝尔曼福特算法时间复杂度比较高(nm)。)
但有边数限制的最短路只能用贝尔曼福特，不能用spfa。(spfa算法一定要求题目中不存在负环。使用Dijkstra不能存在负权边。 )
证明有负环最短路不一定存在：
迭代k次之后，求的最短距离是什么含义，dist数组是什么含义。从1号点经过不超过k条边，走到每个点的最短距离。如果第n次迭代，又更新了某些边，那么就说明存在一条最短路径的变边数是>=n的，是n条边。n条边就意味着有n+1个点，1到n只有n个点，抽屉原理，一定有两个点编号一样，路径上就一定环，路径上存在环就一定是更新过了之后，所以这个环一定是负环。
不一定的证明，存在负权回路也有最短路径：
题目限制了经过的边数不超过k条，所以在负环里不能无限转，最多只能转k次，有负环也就无所谓了。
串联：
> 0x3f3f3f3f /2：
存在负权边，1号点不能到5号点，也不能到n号点。5的+oo可以更新n的+oo，每次+oo-2，就不是0x3f3f3f3f了，但还是很大。题目限制边长绝对值不大于1万，k不大于500，所以最多减500万。所以就写成大于一个比较大的数，表示他到不了。
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int N=510,M=10010;int n,m,k;
int dist[N],backup[N];//backup用于备份上一次的迭代结果。struct Edge{int a, b, w;//a->b，权重w
}edges[M];void bellman_ford(){memset(dist,0x3d,sizeof dist);dist[1]=0;for(int i=0;i<k;i++){//走k条边，每一次迭代向前走一条边memcpy(backup,dist,sizeof dist);//备份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);//取最短路(不超过k条边的)//dist[b]=min(dist[b],dist[a]+w);这样结果是2，就是串联了}}
}int main(){cin>>n>>m>>k;for(int i=0;i<m;i++){int a,b,w;cin>>a>>b>>w;edges[i]={a,b,w};}bellman_ford();if(dist[n] > 0x3f3f3f3f/2) puts("impossible");//大于一个比较大的数else cout<<dist[n]<<endl;return 0;
}
)
