P5960 【模板】差分约束

28pts

#include <bits/stdc++.h>
#define int long long
using namespace std;
int read()
{
	int res = 0,f = 1;
	char ch = getchar();
	while (ch<'0'||ch>'9') f = (ch=='-'?-1:1),ch = getchar();
	while (ch>='0'&&ch<='9') res = (res<<3)+(res<<1)+(ch^48),ch = getchar();
	return res*f;
}
void write(int x)
{
	if (x<0) putchar('-'),x = -x;
	if (x>9) write(x/10);
	putchar(x%10+'0');
}
void writech(int x,char ch){write(x),putchar(ch);}
const int N = 5e3+5;
int n,m;
int e[N],w[N],ne[N],h[N];
int idx;
int dist[N];
bool vis[N];
int cnt[N];
void add(int x,int y,int z)
{
	e[idx]=y;
	w[idx]=z;
	ne[idx]=h[x];
	h[x]=idx++;
}
bool spfa(int s)
{
	for (int i = 1; i < N; i++) dist[i]=2e9;
	memset(vis,false,sizeof(vis));
	memset(cnt,0,sizeof(cnt));
	queue<int>q;
	q.push(s);
	dist[s]=0;
	vis[s]=true;
	while (q.size())
	{
		int u = q.front();
		q.pop();
		vis[u]=false;
		for (int i = h[u]; i != -1; i = ne[i])
		{
			int j = e[i];
			if (dist[j]>dist[u]+w[i])
			{
				dist[j]=dist[u]+w[i];
				cnt[j]=cnt[u]+1;
				if (cnt[j]>=n+1) return true;
				if (!vis[j])
				{
					vis[j]=true;
					q.push(j);
				}
			}
		}
	}
	return false;
}
signed main()
{
	n=read(),m=read();
	memset(h,-1,sizeof(h));
	for (int i = 1; i <= m; i++)
	{
		int x=read(),y=read(),z=read();
		add(y,x,z);
	}
	for (int i = 1; i <= n; i++) add(0,i,0);
	if (spfa(0)) puts("NO");
	else for (int i = 1; i <= n; i++) writech(dist[i],' ');
	return 0;
}