记录编号	138126	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	月考统计	最终得分	100
用户昵称	Iostream3100	是否通过	通过
代码语言	C++	运行时间	0.514 s
提交时间	2014-11-05 17:51:44	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int MAXN=1001+100;
struct edges{
	int e,data;
};
vector <edges> a[MAXN];
int N,M,d[MAXN],v[MAXN];
bool exist[MAXN];
queue <int> q;

void Longest_Path_Faster_Algorithm(void){
	memset(v,0,sizeof(v));
	memset(d,-127/3,sizeof(d));
	memset(exist,false,sizeof(exist));
	d[0]=0;
	edges u;
	u.data=0;
	for(int i=1;i<=N;++i){
		u.e=i;
		a[0].push_back(u);
	}
	++v[0];
	exist[0]=true;
	q.push(0);
	int x,to;
	while(q.size()){
		x=q.front();
		q.pop();
		exist[x]=false;
		for(int i=0;i<a[x].size();++i){
			to=a[x][i].e;
			if(d[to]<d[x]+a[x][i].data){
				d[to]=d[x]+a[x][i].data;
				if(!exist[to]){
					++v[to];
					if(v[to]>N){
						cout<<"SOMEONE LAY!"<<endl;
						return;
					}
					q.push(to);
					exist[to]=true;
				}
			}
		}
	}
	for(int i=1;i<=N;++i){
		cout<<d[i]<<" ";
	}
}
void init(void){
	cin>>N>>M;
	edges u;
	int x;
	for(int i=0;i<M;++i){
		cin>>x>>u.e>>u.data;
		u.data=-u.data;
		a[x].push_back(u);
	}
}
int main(){
	freopen("ExamStat.in","r",stdin);
	freopen("ExamStat.out","w",stdout);
	std::ios::sync_with_stdio(false);
	init();
	Longest_Path_Faster_Algorithm();
}