开发者社区 问答 正文

SPFA在devc上运行出错,C++? 400 报错

SPFA在devc上运行出错,C++? 400 报错

#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("false\n"); } 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……




展开
收起
爱吃鱼的程序员 2020-06-03 16:36:30 463 分享 版权
1 条回答
写回答
取消 提交回答
  • https://developer.aliyun.com/profile/5yerqm5bn5yqg?spm=a2c6h.12873639.0.0.6eae304abcjaIB

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

    2020-06-03 20:49:51
    赞同 展开评论
问答分类:
C++
问答标签:
问答地址: