SPFA在devc上运行出错,C++

发布于 2021-11-28 00:37:02 字数 1872 浏览 758 评论 1

#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#define inf 0x3f3f3f3f
#define MAX 20005
using namespace std;

struct Edge{
	int x,y;
	Edge (int a=0,int b=0):x(a),y(b){};
};

int V,E;				//V结点数,E边数 
vector<Edge> map[MAX];
bool vis[MAX]; 			//是否入队 
int dis[MAX];			//到S的距离。 
int cnt[MAX];			//记录入队次数,判断负环 
queue<int> q;			//用于存储spfa算法中需要松弛的点 

bool spfa(const int S){			//true找到最短路。false存在负环 
	
	memset(vis,false,sizeof(vis));	//vis,dis初始化 
	for(int i=0;i<=V;i++){
		dis[i]=inf;
	}
	dis[S]=0;
	vis[S]=true;
	q.push(S);
	cnt[S]=1;		//1修改入队次数 
	while(!q.empty()){			//队列非空,继续松弛 
		int node=q.front();		//取队首 
		q.pop();
		vis[node]=false;
		for(int i=0;i<map[node].size();i++){
			Edge ed=map[node][i]; 		//vector寻址速度慢,进行寻址优化 
			int t = ed.x;
			int d = ed.y;
			
			if(dis[t] > dis[node]+d){		//距离变小,需要更新 
				int temp=dis[node]+d;
				dis[t] = dis[node]+d;
				if(!vis[t]){
					vis[t]=true;
					q.push(t);
					if(cnt[t]>V){		//2超过V次,有负环 
						while(q.empty()) q.pop();
						return false;
					}
				}
			}			
		}
	}
	return true;			//3
}


int main(){
	scanf("%d%d",&V,&E);
	int u,v,l;
	for(int i=0; i<E; i++){
		scanf("%d%d%d",&u, &v, &l); 
		map[u].push_back(Edge(v,l));
		map[v].push_back(Edge(u,l));
	} 
	if(!spfa(1)){
		//存在负环
		printf("falsen"); 
	}
	else{
		for(int i=1;i<=V;i++)
			printf("%d n",dis[i]);
	} 	
	
	return 0;
}




在spfa()函数的这一行就跳出了,错误提示:


Program received signal SIGSEGV, Segmentation fault.



if(dis[t] > dis[node]+d){		//距离变小,需要更新


求解TT……




如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

葬花如无物 2021-12-01 03:06:51

为毛我复制你的代码在devcpp上能编译通过哦,零错误零警告?

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文