悬赏关注
查看原帖
悬赏关注
881471
RanHT楼主2023/6/25 18:13

为啥边权大于0时要加两条边啊

#include<cstdio>
#include<cstring>
const int maxn=2e3+10;
const int maxm=6e3+10;
int n,m;
struct Edge{
	int to,w,next;
}edge[maxm];        //链式前向星存图
int head[maxn],tot;
inline void Init(){     //有多组测试数据,每次初始化
	for(int i=0;i<maxm;i++) edge[i].next=0;
	for(int i=0;i<maxn;i++) head[i]=0;
	tot=0;
}
inline void addedge(int u,int v,int w){
	edge[++tot].to=v;
	edge[tot].w=w;
	edge[tot].next=head[u];
	head[u]=tot;
}
#include<queue>
using std::queue;
queue<int> Q;
int dis[maxn],vis[maxn],cnt[maxn];
bool spfa(){
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	memset(cnt,0,sizeof(cnt));
	dis[1]=0; vis[1]=true;
	Q.push(1);
	while(!Q.empty()){
		int x=Q.front();
		Q.pop();
		vis[x]=false;
		for(int i=head[x];i;i=edge[i].next){
			int y=edge[i].to,z=edge[i].w;
			if(dis[y]>dis[x]+z){
				dis[y]=dis[x]+z;  //更新最短路
				cnt[y]=cnt[x]+1;  //更新包含边数
				if(cnt[y]>=n) return true;  //判定存在负环
				if(!vis[y]){
					Q.push(y);
					vis[y]=true;
				}
			}
		}
	}
	return false;
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		Init();
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			addedge(u,v,w);
			if(w>=0) addedge(v,u,w);
		}
		puts(spfa()?"YES":"NO");
	}
	return 0;
}
2023/6/25 18:13
加载中...