差分约束

#include<bits/stdc++.h>
using namespace std;
#define N 5010 
int n,m;
vector<int>head,to,nxt,val;
void join(int u,int v,int w)
{
	nxt.push_back(head[u]);
	head[u]=to.size();
	to.push_back(v);
	val.push_back(w);
}
int dis[N],cnt[N];
bool vis[N];
int q[N*N];
bool spfa()
{
	int l=0,r=0;
	for(int i=1;i<=n;++i)
	{
		dis[i]=0x3f3f3f3f;
		cnt[i]=0;vis[i]=0;
	}
	vis[0]=1;dis[0]=0;cnt[0]=1;
	while(l<=r)
	{
		int u=q[l];++l;vis[u]=0;
		for(int i=head[u];i!=-1;i=nxt[i])
		{
			if(dis[to[i]]>dis[u]+val[i])
			{
				dis[to[i]]=dis[u]+val[i];
//				cnt[to[i]]=cnt[u]+1;
//				if(cnt[to[i]]>n) return 0;
				if(!vis[to[i]])
				{
					++cnt[to[i]];
					if(cnt[to[i]]>n) return 0;
					vis[to[i]]=1;
					q[++r]=to[i];
				}
			}
		}
	}
	return 1;
}
int main()
{
	scanf("%d%d",&n,&m);
	head.resize(n+1,-1);
	for(int i=1;i<=n;++i)
	{
		join(0,i,0);
	} 
	for(int i=1;i<=m;++i)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		join(b,a,c);
	}
	if(!spfa()) printf("NO\n");
	else
	{
		for(int i=1;i<=n;++i)
		{
			printf("%d ",dis[i]);
		}
	}
	return 0;
}