可以开一个结构体存储所有边
这个更新的过程叫做松弛操作
bellman-ford算法循环完之后，所有边的距离一定满足
这个叫三角不等式
在求最短路的时候，如果有负权回路的话，最短路是不一定存在的
bellman-ford算法可以求出来是不是有负权回路，负环，时间复杂度O(nm)
第一层for循环的循环次数是有实际意义的
比如说当前迭代了k次
那么我们求的最短距离的含义是：从1号点经过不超过k条边，走到每个点的最短距离
所以如果是第n次迭代的时候，又更新了某些边的话，就说明存在一条最短路径，这条最短路径上的边的个数是n。n条边就有n + 1个点，抽屉原理，一共有两个点一样，一定存在负环
但是一般找负环不用bellman-ford算法，时间复杂度太高，一般用spfa来做
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N = 510, M = 10010; 4 struct edge{ 5 int a, b, w; 6 } edges[M]; //存所有边 7 int n, m, k; 8 int dist[N], backup[N]; 9 //备份 10 int bellman_ford() { 11 memset(dist, 0x3f, sizeof dist); 12 dist[1] = 0; 13 for (int i = 0; i < k; i++) { //迭代k次 14 memcpy(backup, dist, sizeof dist); //防串联 15 //只用上一次更新的结果来更新，防止串联 16 for (int j = 0; j < m; j++) { 17 int a = edges[j].a; 18 int b = edges[j].b; 19 int w = edges[j].w; 20 dist[b] = min(dist[b], backup[a] + w); 21 } 22 } 23 if (dist[n] > 0x3f3f3f3f / 2) { //见注解一，没还不太理解 24 return -1; 25 } 26 return dist[n]; 27 } 28 int main() { 29 cin >> n >> m >> k; 30 for (int i = 0; i < m; i++) { 31 int a, b, w; 32 cin >> a >> b >> w; 33 edges[i].a = a; 34 edges[i].b = b; 35 edges[i].w = w; 36 //edges[i] = {a, b, w}; 37 } 38 int t = bellman_ford(); 39 if (t == -1) { 40 cout << "impossible" << endl; 41 } else { 42 cout << t << endl; 43 } 44 return 0; 45 }
注解一：
比如1号点不能到5号点，1号点也不能到n号点，但是5号点可以到n号点