比赛 |
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;
}