记录编号	137933	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	1787.月考统计	最终得分	100
用户昵称	Ezoi_XY	是否通过	通过
代码语言	C++	运行时间	0.051 s
提交时间	2014-11-05 15:06:33	内存使用	0.42 MiB

#include<cstdio>
#include<cstring>
#include<deque>
using namespace std;
const int V(1011), E(11011);
int h[V], n[E], e[E], w[E], et, d[V], l[V], vt;
bool v[V];
deque<int> q;
inline void ins(int f, int t, int l){
	n[++et] = h[f]; h[f] = et; e[et] = t; w[et] = l;
}
int main(){
	freopen("ExamStat.in", "r", stdin);
	freopen("ExamStat.out", "w", stdout);
	int m, i, j, k;
	scanf("%d%d", &vt, &m);
	while (m--){
		scanf("%d%d%d", &i, &j, &k);
		ins(i, j, -k);
	}
	for (i = 1; i <= vt; ++i) ins(0, i, 0);
	memset(d, 0xd0, sizeof(d)); d[0] = 0;
	q.push_back(0); v[0] = true;
	while (!q.empty()){
		i = q.front(); q.pop_front();
		if (!v[i]) continue; 
		v[i] = false;
		for (j = h[i]; j; j = n[j])
			if (d[e[j]] < d[i] + w[j]){
				if ((l[e[j]] = l[i] + 1) == vt){
					puts("SOMEONE LAY!");
					return 0;
				}
				d[e[j]] = d[i] + w[j];
				v[e[j]] = true;
				if (!q.empty() && d[e[j]] >= d[q.front()]) q.push_front(e[j]);
				else q.push_back(e[j]);
			}
	}
	for (i = 1; i <= vt; ++i) printf("%d ", d[i]);
	return 0;
}