85pts求助
查看原帖
85pts求助
1066207
zongchengxin楼主2024/11/23 13:13
#include <bits/stdc++.h>
using namespace std;
queue<long long> q;
long long s,m,n,vis[100005],cnt[100005],t;
vector<long long> w[100005],e[100005]; 
long long dis[100005];
void spfa(){
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[0]=0;
	vis[0]=1;
	cnt[0]=0;
	q.push(0);
	while(!q.empty()){
		long long x=q.front();
		q.pop(),vis[x]=0;
		for(long long i=0;i<e[x].size();i++){
			long long v=e[x][i];
			if(dis[v]>dis[x]+w[x][i]){
				dis[v]=dis[x]+w[x][i];
				cnt[v]=cnt[v]+1;
				if(cnt[v]>=n+1){
					cout<<"No";
					return ;
				}
				if(!vis[v]){
					q.push(v);
					vis[v]=1;
				}
			}
		}
		
	}
	cout<<"Yes";
	return ;
}

int main(){
	scanf("%lld%lld",&n,&m);
	for(long long i=1;i<=m;i++){
		long long x,y,z,t;
		scanf("%lld%lld%lld",&t,&x,&y);
		if(t==1){
			scanf("%d",&z);
			e[y].push_back(x);
			w[y].push_back(-z); 
		}
		if(t==2){
			scanf("%lld",&z);
			e[x].push_back(y);
			w[x].push_back(z); 
		}else{
			e[y].push_back(x);
			w[y].push_back(0); 
			e[x].push_back(y);
			w[x].push_back(0); 
		}
	}
	for(long long i=1;i<=n;i++) e[0].push_back(i),w[0].push_back(0);
	spfa();
	return 0;
}
2024/11/23 13:13
加载中...