15pts 求条 悬2关
查看原帖
15pts 求条 悬2关
966272
zhs_TLE楼主2025/6/23 22:46
#include<iostream>
#include<vector>
#include<string.h>
#include<queue>
using namespace std;
const int N=5e3+5;
int n,m;
int flag,cnt[N],dis[N];
bool inq[N];
struct edge{
	int to,w;
};
vector<edge> e[N];
void spfa(int s){
	queue<int> q;
	memset(dis,0x7f,sizeof(dis));
	q.push(s);
	inq[s]=1,dis[s]=0;
	while(!q.empty()){
		int now=q.front();
		q.pop();
		for(edge eg:e[now]){
			int v=eg.to,w=eg.w;
			if(dis[v]>dis[now]+w){
				dis[v]=dis[now]+w;
				if(!inq[v])
					q.push(v),inq[v]=1,cnt[v]++;
				if(cnt[v]>=n){
					flag=1;
					return ;
				}
			}
			
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int op,a,b,c;
		cin>>op>>a>>b;
		if(op==1){
			cin>>c;
			e[b].push_back((edge){a,c});
		}
		if(op==2){
			cin>>c;
			e[a].push_back((edge){b,-c});
		}
		if(op==3){
			e[a].push_back((edge){b,0});
			e[b].push_back((edge){a,0});
		}
	}
	for(int i=1;i<=n;i++)
	    e[0].push_back((edge){i,0});
	spfa(0);
	cout<<(flag?"No":"Yes");
	return 0;
}
2025/6/23 22:46
加载中...