文章
1
粉丝
175
获赞
0
访问
7.7k
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...
登录后发布评论
暂无评论,来抢沙发