拓扑排序

#include <iostream>

using namespace std;

const int N = 10000 + 10;
const int M = 10000000 + 10;

int nxt[M], hd[N], to[M];
int ent[N];
int ans[N];
int len[N];

int cnt;
int res;
int n;

inline int (int a, int b)
{
	return a > b ? a : b;
}

inline void add(int x, int y)
{
	to[++cnt] = y;
	nxt[cnt] = hd[x];
	hd[x] = cnt;
	ent[y]++;
}

queue<int> q;

void xhl()
{
	for (int i = 1; i <= n; i++)
	{
		if (ent[i] == 0)
		{
			q.push(i);
			ans[i] = len[i];
		}
	}
	while (q.size())
	{
		int tp = q.front();
		q.pop();
		for (int i = hd[tp]; i; i = nxt[i])
		{
			int x = to[i];
			ent[x]--;
			ans[x] = Max(ans[x], ans[tp] + len[x]);
			if (ent[x] == 0)
			{
				q.push(x);
			}
		}
	}
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int id;
		cin >> id >> len[i];
		int ver;
		while (cin >> ver, ver)
		{
			add(i, ver);
		}
	}
	xhl();
	for (int i = 1; i <= n; i++)
	{
		res = Max(res, ans[i]);
	}
	cout << res << endl;
}