记录编号	137958	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	月考统计	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.953 s
提交时间	2014-11-05 15:22:10	内存使用	0.30 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int SIZEN=1010;
int N,M;
vector<pair<int,int> > c[SIZEN];
int f[SIZEN];
int cnt[SIZEN];
bool inq[SIZEN];
queue<int> Q;
bool SPFA(void){//最长路
	memset(f,0,sizeof(f));
	for(int i=1;i<=N;i++) inq[i]=true,Q.push(i),cnt[i]=1;
	while(!Q.empty()){
		int x=Q.front();Q.pop();inq[x]=false;
		//cout<<x<<" "<<c[x].size()<<endl;
		for(int i=0;i<c[x].size();i++){
			int u=c[x][i].first;
			//cout<<x<<" "<<i<<" "<<u<<endl;
			//if(x==3&&u==2) cout<<c[x][i].second<<" "<<f[x]<<" "<<f[u]<<endl;
			if(f[x]+c[x][i].second>f[u]){
				//cout<<x<<" "<<u<<endl;
				f[u]=f[x]+c[x][i].second;
				if(!inq[u]){
					if(cnt[u]>=N) return false;
					cnt[u]++;
					inq[u]=true;
					Q.push(u);
				}
			}
		}
	}
	return true;
}
void work(void){
	if(!SPFA()){
		printf("SOMEONE LAY!\n");
	}
	else{
		for(int i=1;i<=N;i++) printf("%d ",f[i]);
		printf("\n");
	}
}
void init(void){
	scanf("%d%d",&N,&M);
	int x,y,a;
	for(int i=1;i<=M;i++){
		scanf("%d%d%d",&x,&y,&a);
		c[x].push_back(make_pair(y,-a));
		//cout<<x<<" "<<y<<" "<<-a<<endl;
	}
}
int main(){
	freopen("ExamStat.in","r",stdin);
	freopen("ExamStat.out","w",stdout);
	init();
	work();
	return 0;
}