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()函数的这一行就跳出了,错误提示:
if(dis[t] > dis[node]+d){ //距离变小,需要更新
求解TT……
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。
为毛我复制你的代码在devcpp上能编译通过哦,零错误零警告?