您当前的位置: 首页 >  算法

不牌不改

暂无认证

  • 0浏览

    0关注

    422博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

Bellman_ford算法解决负边权与有边数限制的最短路问题模板

不牌不改 发布时间:2022-03-15 20:28:59 ,浏览量:0

题目链接

解决单源最短路问题,存在负边权,时间复杂度 O ( n m ) O(nm) O(nm)

计算最多经过k步,从1到n的最小权重和。

#include
using namespace std;

const int N = 510, M = 10010, INF = 0x3f3f3f3f;

int n, m, k;
int d[N], backup[N];

struct edge {
	int a, b, w;
} e[M]; 

void bellman_ford () {
	
	memset (d, 0x3f, sizeof d); // 注意初始化 
	d[1] = 0;
	
	for (int i = 1;i  n >> m >> k;
	for (int i = 0;i > a >> b >> w;
		e[i] = {a, b, w};
	}
	
	bellman_ford ();
	
	if (d[n] > INF / 2) puts ("impossible"); // 存在负边权,可能会导致INF加上负边权而变小,所以不可以用等于INF来判断。
	else cout             
关注
打赏
1662186765
查看更多评论
0.7628s