AC#1,#12,#20,求调,悬关
查看原帖
AC#1,#12,#20,求调,悬关
1123452
czh___楼主2024/7/8 16:18
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5*1e3+1;
int n,m,head[N],vis[N],d[N],tot[N],cnt;
queue<int>q;
struct aaa{
	int v,w,next;
}e[N];
void jt(int u,int v,int w){
	e[++cnt].v=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int p,a,b,c;
		cin>>p;
		if(p==1){
			cin>>a>>b>>c;
			jt(b,a,c);
		}
		if(p==2){
			cin>>a>>b>>c;
			jt(a,b,-c);
		}
		if(p==3){
			cin>>a>>b;
			jt(a,b,0);
			jt(b,a,0);
		}
	}
	for(int i=1;i<=n;i++)
		jt(0,i,0);
	q.push(0);
	memset(d,-0x3f,sizeof(d));
	while(!q.empty()){
		int o=q.front();
		q.pop();
		for(int i=head[o];i;i=e[i].next){
			if(d[o]+e[i].w>d[e[i].v]){
				d[e[i].v]=d[o]+e[i].w;
				if(!vis[e[i].v]){
					vis[e[i].v]=1;
					tot[e[i].v]++;
					q.push(e[i].v);
					if(tot[e[i].v]>=n){
						cout<<"No";
						return 0;
					}
				}
			}
		}
	}
	cout<<"Yes";
	return 0;
}
2024/7/8 16:18
加载中...