live archive 4267 - Finding The Heaviest Path

[f74956227]

Could someone help me with the problem??? I always got WA (about 50 times...) ! Could someone help me with my code? please

Code: Select all

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <memory.h>
#define MAX 10010
using namespace std;

int root, N, ansnum;
int ans[MAX], outdeg[MAX], C[MAX], W[MAX], path[MAX];
bool isfind[MAX];
vector<int>adj[MAX];

int dp(int now)
{
	//a leaf node
	if(outdeg[now]==0)
		return W[now];

	//if is found
	if(isfind[now]) return C[now];

	//top-down
	int i, next, w, best;

	for(i=0; i<(int)adj[now].size(); i++)
	{
		next = adj[now][i];

		//if(next==parent)continue;

		w = dp(next);

		if(i==0 || w>best)
			best = w, path[now] = next;
		else if(w==best)
			path[now] = max(path[now], next);
	}

	if( adj[now].size()==0 )	best = 0;
	C[now] = W[now] + best;

	//memorized
	isfind[now] = true;
	return C[now];
}

int main()
{
	//freopen("4267", "r", stdin);

	int i, j, k, c, datacase, cost;
	scanf("%d", &datacase);

	while(datacase--)
	{
		//clear the data
		for(i=0; i<MAX; i++) adj[i].clear();

		scanf("%d %d", &N, &root);

		//read the tree information
		memset(outdeg, 0, sizeof(outdeg));
		for(i=0; i<N; i++)
		{
			scanf("%d %d", &W[i], &j);

			//the children of node number i
			for(k=0; k<j; k++)
			{
				scanf("%d", &c);
				adj[i].push_back(c);
				outdeg[i]++;

				//adj[c].push_back(i);
			}
		}

		//start to find the path and max-cost path
		for(i=0; i<MAX; i++)
			isfind[i] = false, C[i] = 0, path[i] = -1;

		cost = dp(root);
		printf("%d", cost);

		//find the path (root to leaf)
		ansnum = 0, ans[ansnum++] = root;

		while(path[root]!=-1)
		{
			ans[ansnum++] = path[root];
			root = path[root];
		}

		for(i=0; i<ansnum; i++)
		{
			if(i%10==0)
				printf("\n%d", ans[i]);
			else
				printf(" %d", ans[i]);
		}
		putchar('\n');

	}
	return 0;
}