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

星琳 发布于 2016/05/14 11:54
阅读 160
收藏 0
#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……




加载中
0
熳卟
熳卟
为毛我复制你的代码在devcpp上能编译通过哦,零错误零警告?
返回顶部
顶部