差分约束 spfa 全是yes 15pts求调
查看原帖
差分约束 spfa 全是yes 15pts求调
1033449
kevinf楼主2023/10/29 11:14
#include<bits/stdc++.h>
using namespace std;
struct road{
	int v,w;
	road(){}
	road(const int &v,const int &w):v(v),w(w){}
};
vector<road> v[100005];
int dis[100005],cnt[100005];
bool vis[100005];
queue<int> q;
int c=0;
int main(){
	int n,m,ta,tb,tc,start=0,k;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d",&k);
		if(k==1){
			scanf("%d%d%d",&ta,&tb,&tc);
			v[tb].emplace_back(ta,c);
		}else if(k==2){
			scanf("%d%d%d",&ta,&tb,&tc);
			v[ta].emplace_back(tb,-c); 
		}else if(k==3){
			scanf("%d%d",&ta,&tb);
			v[ta].emplace_back(tb,0);
			v[tb].emplace_back(ta,0);
		}
	}
	for(int i=1;i<=n;i++) v[0].emplace_back(i,0);
	for(int i=1;i<=n;i++) dis[i]=0x3fffffff;
	dis[start]=0;
	vis[start]=true;
	q.emplace(start);
	while(q.size()){
		int r=q.front();
		q.pop();
		vis[r]=false;
		for(auto i:v[r]){
			if(dis[i.v]>dis[r]+i.w){
				dis[i.v]=dis[r]+i.w;
				if(!vis[i.v]){
					if(++cnt[i.v]>n){
						printf("No\n");
						return 0;
					}
					vis[i.v]=true;
					q.emplace(i.v);
				}
			}
		}
	}
	printf("Yes\n");
	return 0;
}

2023/10/29 11:14
加载中...