文章

1

粉丝

175

获赞

0

访问

7.6k

头像
SPFA解法及两点注意
P1286 上海交通大学机试题
发布于2021年8月30日 21:37
阅读数 7.6k

1.如果点a到b已连通,那么再遇到a到b的边就不应该再加入,因为2^k>1+2^1+.......+2^k-1,如果无脑添加的话就会有数据点出错,这跟通用的最短路径解法有出入,但是为什么加入会出错我搞不懂求大佬解释,因为遍历的话应该能算出最小路径啊,难道它的数据点里有重复的边......

2.数据溢出问题 每次加入两点距离时都应该%100000,否则一直累加就会数据溢出。

#include<bits/stdc++.h>
using  namespace std;
#define inf 0x3f3f3f3f
const int maxn = 105;
struct edge {
	int u, v, w;
};
vector<edge>edges;
vector<int>g[maxn];
int dis[maxn];
int v[maxn];
int p[maxn];
int m, n;
int fa[maxn];
int find(int x) {
	if (x == fa[x])return x;
	fa[x] = find(fa[x]);
	return fa[x];
}
void SFPA(int x) {
	memset(v, 0, sizeof(v));
	for (int i = 0;i < n;i++) {
		dis[i] = inf;
	}
	queue<int> q;
	q.push(x);
	dis[x] = 0;//别忘了设置本距离是零
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		v[u] = 0;
		for (int i = 0;i < g[u].size();i++) {
			edge& e = edges[g[u][i]];
			if (dis[e.v] > dis[u] + e.w) {
				dis[e.v] = dis[u] + e.w;
				p[e.v] = u;
				if (v[e.v] == 0) {
					v[e.v] = 1;
					q.push(e.v...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发