差分约束板子求调qwq
查看原帖
差分约束板子求调qwq
379113
dtrthg楼主2024/6/20 19:22

rt

#include <bits/stdc++.h>
using namespace std;
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define of(i,a,b) for(int i=a;i>=b;--i)
#define ll long long
#define P_B push_back
const int inf=0x3f3f3f3f;
const ll INF=9e18;
//const ll mod=;
const int N=5e3+10,M=1e4+10;
struct Node{int v,val;};
vector <Node> no[N];
bool vis[N];
int cnt[N],dis[N];
bool spfa(int n)
{
	memset(dis,0x3f,sizeof(dis));
	dis[0]=0; vis[0]=1;
	queue <int> q;
	q.push(0);
	while(!q.empty())
	{
		int now=q.front(); q.pop();
		vis[now]=0;
		int sze=no[now].size();
		for(int i=0;i<sze;++i)
		{
			int nxt=no[now][i].v,val=no[now][i].val;
			if(dis[nxt]>dis[now]+val)
			{
				dis[nxt]=dis[now]+val;
				cnt[nxt]=cnt[now]+1;
				if(cnt[nxt]>=n+1) return 1;
				if(!vis[nxt]) {q.push(nxt); vis[nxt]=1;}
			}
		}
	}
	return 0;
}
int main()
{
	ios::sync_with_stdio(0);
	int n,m;cin>>n>>m;
	fo(i,1,n)
	{
		int op;cin>>op;
		if(op==1)
		{
			int u,v,w;cin>>u>>v>>w;
			Node rr; rr.v=v; rr.val=-w;
			no[u].P_B(rr);
		}
		if(op==2)
		{
			int u,v,w;cin>>u>>v>>w;
			Node rr; rr.v=u; rr.val=w;
			no[v].P_B(rr);
		}
		if(op==3)
		{
			int u,v;cin>>u>>v;
			Node rr; rr.v=v; rr.val=0;
			no[u].P_B(rr);
			rr.v=u;
			no[v].P_B(rr);
		}
	}
	fo(i,1,n) no[0].P_B({i,0});
	if(spfa(n)) cout<<"No"<<endl;
	else cout<<"Yes"<<endl;
	return 0;
}
/*
in1:
3 3
3 1 2
1 1 3 1
2 2 3 2
out1:
Yes
*/
2024/6/20 19:22
加载中...