救命!!!!第一次写spfa样例过不去
查看原帖
救命!!!!第一次写spfa样例过不去
499140
3wykx楼主2023/8/7 14:53

样例输入,结果输出0和两个无穷大数

啊啊,谁能救命啊啊

#include <bits/stdc++.h>
using namespace std;
struct Edge{
	int to,dis,nxt;
}edge[5005];
int num_edge,n,m,u,v,w;
int head[5005],d[5005],visit[5005],cnt[5005];
void add_edge(int from,int to,int dis){
	edge[++num_edge].nxt=head[from];
	edge[num_edge].to=to;
	edge[num_edge].dis=dis;
	head[from]=num_edge;
}
bool spfa(){
	queue<int> q;
	q.push(1);
	d[1]=0;cnt[1]++;visit[1]=1;
	for(int i=2;i<=n;i++){
		q.push(i);
		visit[i]=1;
		cnt[i]++;
	}
	while(!q.empty()){
		int x=q.front();
		q.pop();
		visit[x]=0;
		for(int i=head[x];i;i=edge[i].nxt){
			int nto=edge[i].to,ndis=edge[i].dis;
			if(d[nto]>d[x]+ndis){
				d[nto]=d[x]+ndis;
				if(!visit[nto]){
					q.push(nto);
					visit[nto]=1;
					cnt[nto]++;
					if(cnt[nto]>n)return false;
				}
			}	
		}
	}
	return true;
}
int main(){
	memset(d,0x3f,sizeof(d));
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		add_edge(v,u,w);
	}
	if(spfa()){
		for(int i=1;i<=n;i++)
			cout<<d[i]<<' ';
	}else{
		cout<<"NO"<<endl;
	}
	return 0;
}
2023/8/7 14:53
加载中...