记录编号	348261	评测结果	AAAAAAA
题目名称	[NOIP 2003]神经网络	最终得分	100
用户昵称	小e	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2016-11-14 06:28:02	内存使用	0.58 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

const int maxnumber = 210;
int n, m;
struct Edge
{
	int to, w, next;
}edges[maxnumber * maxnumber];
int head[maxnumber], tot;
int u[maxnumber], c[maxnumber];
int indegree[maxnumber], outdegree[maxnumber];

inline void AddEdge(const int& from, const int& to, const int& w)
{
	edges[++tot].to = to;
	edges[tot].w = w;
	edges[tot].next = head[from];
	head[from] = tot;
}

inline void BFS()
{
	queue <int> Q;
	for (int i = 1; i <= n; ++i)
		if (!indegree[i]) Q.push(i);
	while (!Q.empty()) {
		int front = Q.front(); Q.pop();
		if (c[front] <= 0) continue;
		for (int i = head[front]; i; i = edges[i].next) {
			int to = edges[i].to, w = edges[i].w;
			c[to] += w * c[front];
			indegree[to]--;
			if (!indegree[to]) {
				c[to] -= u[to];
				Q.push(to);
			}
		}
	}
}

#define SUBMIT
int main(int argc, char const *argv[])
{
#ifdef SUBMIT
	freopen("sjwl.in", "r", stdin); freopen("sjwl.out", "w", stdout);
#endif

	int from, to, w;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i)
		scanf("%d%d", &c[i], &u[i]);
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d%d", &from ,&to, &w);
		AddEdge(from, to, w);
		indegree[to]++; outdegree[from]++;
	}

	BFS();

	// for (int i = 1; i <= n; ++i)
	// 	if (!outdegree[i]) printf("c[%d]:%d ", i, c[i]); printf("\n");
	bool flag = 0;
	for (int i = 1; i <= n; ++i)
		if (!outdegree[i] && c[i] > 0) { flag = 1; printf("%d %d\n", i, c[i]); }
	if (!flag) printf("NULL\n");

#ifndef SUBMIT
	printf("\n----------\n");
	getchar(); getchar();
#else
	fclose(stdin); fclose(stdout);
#endif

	return 0;
}