#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int N;
int* cost;
int* d;
int* v;
struct CHOR
{
	int dest;
	CHOR* next;
}chor[10001];

void inser(int x, int y )
{
	CHOR* p;
	p = new CHOR;
	p->dest = y;
	p->next = chor[x].next;
	chor[x].next = p;
}


void djs(int start)
{
	if(chor[start].next==NULL) {d[start]=cost[start]; return;}

	CHOR* p = chor[start].next;
	int max = -1;
	while(p)
	{
		if(d[p->dest]==-1) djs(p->dest);
		//cout << p->dest << " " << d[p->dest] << endl;
		max = max>d[p->dest]?max:d[p->dest]+cost[start];
		p = p->next;
	}
	d[start] = max;
	return;
}

int main()
{
	scanf("%d",&N);
	cost = new int[N+1];
	d = new int[N+1];
	
	memset(chor,0,sizeof(chor));
	for(int i = 1;i <= N;i++)
	{
		d[i] = -1;
	}

	for(int i = 1;i <= N;i++)
	{
		int n;
		scanf("%d %d",&cost[i],&n);	
	
		for(int j = 1; j <= n;j++)
		{
			int y;
			scanf("%d",&y);
			inser(i,y);
		}
	}

	for(int i = N;i >= 1;i--)
	{
		if(d[i]==-1)
		{
			djs(i);
		}
	}
	int max = -1;
	for(int i = 1;i <= N;i++)
		max = max>d[i]?max:d[i];

	cout << max << endl;

	return 0;
}

• Re:哪位神帮我看下吧，，，我想不通啊，，，这个是水题啊 (1338) 547880119 2009-09-16 10:03:18