比赛 20110318 评测结果 AWWWWWWWWW
题目名称 工程规划 最终得分 10
用户昵称 Pom 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-03-18 19:44:55
显示代码纯文本
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

const int MAXN=2000;
const int MAXM=20000;
const int S=0;
const int M=MAXN+10;
const int oo=1000000000;

struct edge
{
	int t,c;
	edge *p;
}e[MAXM],*v[MAXN];

int n,m,i,j,k,Q[MAXN*2],d[MAXN],es=-1;
bool used[MAXN];

inline void addedge(int i,int j,int c)
{
	e[++es].t=j; e[es].c=c; e[es].p=v[i]; v[i]=e+es;
}

bool pd(int u,int now)
{
	used[u]=true;
	for (edge *x=v[u];x;x=x->p)
		if (x->t==i && x->c+now<0) return false;
		else
			if (!used[x->t]) return pd(x->t,now+x->c);
	return true;
}

void spfa()
{
	int t,s,h;
	s=t=h=1;
	Q[t]=0;
	for (i=1;i<=n;i++) d[i]=oo;
	d[S]=0;
	memset(used,false,sizeof(used));
	used[S]=true;
	while (s)
	{
		k=Q[h];
		for (edge *x=v[k];x;x=x->p)
			if (x->c+d[k]<d[x->t])
			{
				d[x->t]=x->c+d[k];
				if (!used[x->t])
				{
					t=(t+1)%M;
					Q[t]=x->t;
					used[x->t]=true;
					++s;
				}
			}
		used[k]=false;
		h=(h+1)%M;
		--s;
	}
}

int main()
{
	freopen("work.in","r",stdin);
	freopen("work.out","w",stdout);
	scanf("%d%d",&n,&m);
	while (m--)
	{
		scanf("%d%d%d",&i,&j,&k);
		addedge(j,i,k);
	}
	for (i=1;i<=n;i++)
	{
		addedge(S,i,0);
	}
	for (i=1;i<=n;i++)
	{
		memset(used,false,sizeof(used));
		if (!pd(i,0))
		{
			printf("NO SOLUTION\n");
			return 0;
		}
	}
	spfa();
	j=oo;
	for (i=1;i<n;i++)
	{
		if (d[i]<j)
		{
			j=d[i];
			k=i;
		}
	}
	for (i=1;i<=n;i++)
	{
		d[i]-=j;
	}
	for (i=1;i<=n;i++)
		printf("%d\n",d[i]);
	return 0;
}