写错哪了
查看原帖
写错哪了
355093
离·清梦楼主2022/6/15 22:39

没写完代码,发现判断负环这里就写错了

大佬们,我哪里写错了?

#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e9;
int cnt,n,m,head[3010],sum[3010],diss[3010],disd[3010];
bool vis[3010];
struct qedge{
	int to,nextt,quan;
}edge[6010];
void addedge(int x,int y,int z){
	edge[++cnt].to = y;
	edge[cnt].quan = z;
	edge[cnt].nextt = head[x];
	head[x] = cnt;
}
queue<int> q;
bool spfa(int x){
	for(int i = 1;i <= n;i++) diss[i] = inf;
	q.push(x);
	diss[x] = 0;
	vis[x] = 1; 
	sum[x]++;
	while(!q.empty()){
		int u = q.front();
		vis[u] = 0;
		q.pop();
		for(int i = head[u];i;i = edge[i].nextt){
			int v = edge[i].to;
			if(diss[v] > diss[u] + edge[i].quan){
				diss[v] = diss[u] + edge[i].quan;
				if(!vis[v]){
					q.push(v);
					vis[v] = 1;
					sum[v]++;
					if(sum[v] == n + 1) return true;
				}
			}
		}
	} 
	return false;
}
struct node{
	int id,dis;
	bool operator < (const node &x)const{
		return x.dis < dis; 
	} 
}; 
queue<node> qq;
//void dij
int main(){
	cin>>n>>m;
	for(int i = 1;i <= m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		addedge(a,b,c);
	}
	for(int i = 1;i <= n;i++){
		addedge(0,i,0);
	}
	if(spfa(n + 1)){
		cout<<-1;
		return 0;	
	}
} 
2022/6/15 22:39
加载中...