有边数限制的最短路

题目描述：

给定一个n个点m条边的有向图，图中可能存在重边和自环，

边权可能为负数

。

请你求出从1号点到n号点的

最多经过 k 条边的最短距离

，如果无法从1号点走到n号点，输出impossible。

注意：图中可能

存在负权回路

。

模板理解：

此算法主要针对有边数限制的最短路，由于两点之间有边数限制，所以干脆就迭代k次，每次循环 m 条边，即使有负环存在，也最多迭代k次就会退出。同Floyd一样，由于存在负边，原本两两点之间不存在通路，但迭代过后，dis可能会小于初始化的 INF，所以注意判断条件。

复杂度：O(n*m)


Code：

#include<bits/stdc++.h>

using namespace std;
const int M = 1e5+7 , N = 510;

int dis[N],last[N];
int n,m,k;

struct Edge{
	int x,y,w;
}ed[M];

void bellman_ford()
{
	memset(dis,0x3f,sizeof dis);
	dis[1] = 0;
	
	for(int i=0;i<k;i++){
		memcpy(last , dis , sizeof dis);	//注意这里的操作
		for(int j=0;j<m;j++){
			Edge t = ed[j];
			dis[t.y] = min(dis[t.y],last[t.x] + t.w);		//使用上一个状态的 dis 迭代
		}	
	}
}

int main()
{
	cin>>n>>m>>k;
	for(int i=0;i<m;i++){
		scanf("%d%d%d",&ed[i].x,&ed[i].y,&ed[i].w);
	}
	bellman_ford();
	if(dis[n] > 0x3f3f3f3f/2) printf("impossible\n");
	else printf("%d\n",dis[n]);
	return 0;
}