SPFA在devc上运行出错,C++
#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 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(1)
为毛我复制你的代码在devcpp上能编译通过哦,零错误零警告?