bellman-ford算法求K短路O(n*m)，以及判负环O(n*m)

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int N=510,M=1e4+10;int n,m,k,dis[N],backup[N];
//dis数组表示dis[i]到起点的距离。struct
{
int a,b,w;
}edge[M];//bellman-ford可以求出来图中有没有负权回路。//迭代k次返回的数表示：从起点经过不超过k条边到各个点的最短距离/*
bellman-ford可以判断负环O(n*m)，如果第n次迭代仍然有更新，则说明找到
了n条边的最短路径，如果一条最短路径上有n条边，
即有n+1个点，根据抽屉原理，说明有负环。一般用spfa算法判断负环
*/
int bellman_ford()//直接返回k短路的距离，当k==m时返回起点到终点的最短距离
{
memset(dis,0x3f,sizeof dis);
dis[1]=0; for(int i=0;i<k;i++)//k次迭代，没次迭代每次得到一个
//到起点的最近的邻居点。
{
//防止出现串联的情况
memcpy(backup,dis,sizeof dis);
for(int j=0;j<m;j++)//枚举所有的m条边
{
int a=edge[j].a,b=edge[j].b,w=edge[j].w;
dis[b]=min(dis[b],backup[a]+w);
}
} if(dis[n]>0x3f3f3f3f/2)return -1;
return dis[n];}int main()
{
cin>>n>>m>>k;
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].w);
}
int t=bellman_ford();
if(t==-1)
cout<<"impossible";
else
cout<<t;
return 0;
}