记录编号	138525	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	月考统计	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.821 s
提交时间	2014-11-05 21:57:27	内存使用	1.43 MiB

#include<fstream>
#include<deque>
using namespace std;
ifstream input("ExamStat.in");
ofstream output("ExamStat.out");
deque<int> q,s[1010],p[1010];
int pan=0,de[1010]={0},n,m,cnt[1010]={0};
int long_way[1010]={0};
int SPFA()
{
	for(int i=1;i<=n;i++) de[i]=1,q.push_back(i),cnt[i]=1;
	while(!q.empty())
	{
		int x=q.front();
		q.pop_front();
		de[x]=0;
		for(int i=0;i<s[x].size();i++)
		{
			int u=s[x][i];
			if(long_way[x]+p[x][i]>long_way[u])
			{
				long_way[u]=long_way[x]+p[x][i];
				if(!de[u])
				{
					if(cnt[u]>=n) return 1;
					de[u]=1;
					cnt[u]++;
					q.push_back(u);
				}
			}
		}
	}
	return 0;
}
int main()
{
	int i;
	input>>n>>m;
	for(i=1;i<=m;i++)
	{
	int a,b,c;
	input>>a>>b>>c;
	s[a].push_back(b);
	p[a].push_back(-c);
	}
	if(SPFA()==1)
	{
		output<<"SOMEONE LAY!";
	}
	else
		for(i=1;i<=n;i++)
			output<<long_way[i]<<" ";
	input.close();
	output.close();
	return 0;
}