適用場景：有邊數限制?->（有負環也就沒影響了），存在負權邊，O( n * m )；

有負權回路時有的點距離會是負無窮，因此最短路存在的話就說明沒有負權回路。

從1號點經過不超過k條邊到每個點的距離。

若經過n次迭代，有更新的話（經過n+1個點了）就說明存在負環（一般不用其來求，用SPFA來判斷負環）。

只有負環在1號點到n號點的路徑上時，最短路才會不存在，在別的路上不影響。

有負環不會死循環，但是值可能會很小

#include<bits/stdc++.h>
using namespace std;
const int N=510,M=10010;
int n,m,k;
int dist[N],backup[N];
struct edge{int a,b,w;
}edges[N];
int bellman_ford(){memset(dist,0x3f,sizeof dist);dist[1]=0;for(int i=0;i<k;++i){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;dist[b]=min(dist[b],backup[a]+w);}}if(dist[n]>0x3f3f3f3f / 2 ) return -1; //除2的原因是可能存在負權邊return dist[n];
}
int main(){scanf("%d%d%d",&n,&m,&k);for(int i=0;i<m;++i){int a,b,w;scanf("%d%d%d",&a,&b,&w);edges[i]={a,b,w};}int t=bellman_ford();if(t==-1) puts("impossible");else printf("%d\n",t);return 0;
}