bellman-ford是一个可以求带负权边的单源最短路，但是时间复杂度是铁定的O(nm)，所以我们一般用他的优化版本SPFA，不过由于bellman-ford算法的流程，它也可以用来解决一类特定的问题

那就是求出起点到其他点经过不大于k条边的最短路径

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 int n,m,k;
 5 const int N=510;
 6 const int M=10010;
 7 struct edges{
 8     int a,b,w;
 9 }edges[M];
10 int dis[N],backup[N];
11 int bellman_ford(){
12     memset(dis,0x3f,sizeof(dis));
13     dis[1]=0;
14     for(int i=0;i<k;i++){
15         memcpy(backup,dis,sizeof(dis));
16         for(int j=0;j<m;j++){
17             auto t=edges[j];
18             if(backup[t.a]!=0x3f3f3f3f&&dis[t.b]>backup[t.a]+t.w){
19                 dis[t.b]=backup[t.a]+t.w;
20             }
21         }
22     }
23     return dis[n];
24 }
25 int main(void){
26     cin>>n>>m>>k;
27     for(int i=0;i<m;i++){
28         int a,b,c;
29         cin>>a>>b>>c;
30         edges[i]={a,b,c};
31     }
32     int res=bellman_ford();
33     if(res==0x3f3f3f3f) cout<<"impossible";
34     else cout<<res;
35     return 0;
36 }