对了3个点......
查看原帖
对了3个点......
660243
shenmeyebuhui楼主2023/5/5 17:32
#include<bits/stdc++.h>
using namespace std;
struct edge
{
	int v,cost;
};
queue<int>q;
vector<edge>G[5010];
int n,m,vis[5010],dist[5010],cnt[5010];
int spfa()
{
	for(int i=1;i<=n;i++)
	{
		dist[i]=1e9;
	}
	vis[0]=1;
	cnt[0]=1;
	q.push(0);
	dist[0]=0;
	while(q.empty()==0)
	{
		int now=q.front();
		q.pop();
		vis[now]=0;
		for(int i=0;i<G[now].size();i++)
		{
			edge e=G[now][i];
			if(dist[e.v]>dist[now]+e.cost)
			{
				dist[e.v]=dist[now]+e.cost;
				if(vis[e.v]==0)
				{
					cnt[e.v]++;
					vis[e.v]=1;
					q.push(e.v);
					if(cnt[e.v]>=n+1)
					{
						return 1;
					}
				}
			}
		}
	}
	return 0;
}
int main()
{
	cin>>n>>m;
	while(m--)
	{
		int num;
		if(num==1)
		{
			int a,b,c;
			cin>>a>>b>>c;
			edge e;
			e.v=a;
			e.cost=-c;
			G[b].push_back(e);
		}
		if(num==2)
		{
			int a,b,c;
			cin>>a>>b>>c;
			edge e;
			e.v=a;
			e.cost=c;
			G[b].push_back(e);
		}
		if(num==3)
		{
			int a,b;
			cin>>a>>b;
			edge e;
			e.v=a;
			e.cost=0;
			G[b].push_back(e);
		}
	}
	for(int i=1;i<=n;i++)
	{
		edge e;
		e.v=i;
		e.cost=0;
		G[0].push_back(e);
	}
	if(spfa()==1)
	{
		cout<<"No"<<endl;
	}
	else
	{
		cout<<"Yes"<<endl;
	}
	return 0;
}
2023/5/5 17:32
加载中...