算法思想
Bellman-Ford算法构造一个最短路径长度数组序列dist1[u], dist2[u], …, distn-1[u]。其中：
dist1[u]为从源点v到终点u的只经过一条边的最短路径长度，并有dist1[u]=Edge[v][u]；
dist2[u]为从源点v最多经过两条边到达终点u的最短路径长度；
dist3[u]为从源点v出发最多经过不构成负权值回路的三条边到达终点u的最短路径长度；
……
distn-1[u]为从源点v出发最多经过不构成负权值回路的n-1条边到达终点u的最短路径长
度；
算法的最终目的是计算出distn-1[u]，为源点v到顶点u的最短路径长度。
dist k [u]的计算
采用递推方式计算distk[u]：
1、 设已经求出 distk-1[u]
2、从图的邻接矩阵找到各个顶点j到达顶点u的距离Edge[ j][u]，计算 min{distk-1[j]+Edge[j][u]}，可得从源点v经过各个顶点，最多经过不构成负权值回路的k条边到达终点u的最短路径的长度；
2、比较distk-1[u]和min{distk-1[j]+Edge[j][u]} ，取较小者作为distk[u]的值。
Bellman算法和dijkstra算法的区别
Dijkstra算法在求解过程中，源点到集合S内各顶点的最短路径一旦求出，之后就不变了，修改的仅仅是源点到T集合中各顶点的最短路径长度。
Bellman算法在求解过程中，每次循环都要修改所有顶点的dist[ ]，源点到各顶点最短路径长度一直要到Bellman算法结束才能确定。
Bellman算法判断负权回路思想
如果存在从源点可达的负权值回路，则最短路径不存在，因为可以重复走这个回路，使得路径无穷小。
在Bellman算法中判断是否存在从源点可达的负权值回路的方法：
在求出distn-1[ ]之后，再对每条边<u,v>判断一下（即distn[ ])：加入这条边是否会使得顶点v的最短路径再缩短，即判断：dist[u]+Edge(u,v)<dist[v]是否成立，如果成立，则说明存在从源点可达的负权值回路。
for (i=0;i<n;i++) { for (j=0;j<n;j++) { if (Edge[i][j]<MAX && dist[j]>dist[i]+Edge[i][j]) return 0;//存在从源点可达的负权值回路 }
}
return 1;假设源为k，当i = k且j = k时判断了dist(k->k)的路径。是否必要呢？
答案是必要！若存在负权回路，源点的距离也可能缩短
复杂度分析
n个顶点e条边，三重for循环
（1）使用邻接矩阵O(n^2)
(2) 使用邻接表,最多考查每条边 n 次,O(ne)
#include<iostream>
#include<algorithm>
#include<cstring>
const int M = 1e4 + 10, N = 510;
using namespace std;
int dist[N];
int last[N];
int n, m, k;struct Edge
{int a, b, c;
}edges[M];void bellman_fold()
{memset(dist, 0x3f, sizeof dist);dist[1] = 0;for(int i = 0; i < k; i++){memcpy(last, dist, sizeof dist);for(int j = 0; j < m; j++){auto e = edges[j];dist[e.b] = min(dist[e.b], last[e.a] + e.c);//}}
}int main()
{cin >> n >> m >> k;for(int i = 0; i < m; i++){int a, b, c;cin >> a >> b >> c;edges[i] = {a, b, c};}bellman_fold();if(dist[n] > 0x3f3f3f3f / 2) puts("impossible");else cout << dist[n] << endl;return 0;
}