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

#include<cstdio>
#include<cstring>
#include<deque>
using namespace std;
const int V(1011), E(10011);
int h[V], n[E], e[E], w[E], et, d[V], l[V], v[V], now, vt, a[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(j, i, k);
	}
	for (now = 1; now <= vt; ++now){
		memset(d, 0x3f, sizeof(d)); d[now] = 0;
		l[now] = 0;
		q.clear(); q.push_back(now); v[now] = now;
		while (!q.empty()){
			i = q.front(); q.pop_front();
			if (v[i] != now) continue;
			v[i] = 0;
			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]] = now;
					q.push_back(e[j]);
//					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)
			if (a[now] < -d[i]) a[now] = -d[i];
	}
	for (i = 1; i <= vt; ++i) printf("%d ", a[i]);
	return 0;
}