Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

我的代码TLE了,谁能给点提示啊

Posted by azhu981712 at 2009-11-19 15:45:50 on Problem 1935
#include <iostream>
#include <set>
using namespace std;

struct Node
{
	int num;
	int dist;
	Node* next;
};

int n,start,k;
Node* map[50001];
bool vis[50001];
set<int> tar;

void Insert(int a,int b,int d)
{
	Node* tmp=new Node;
	tmp->num=b;
	tmp->dist=d;
	tmp->next=map[a];
	map[a]=tmp;
}

void DelMap()
{
	int i;
	Node* tmp;
	Node* tmp2;

	for(i=1;i<=n;i++)
	{
		tmp=map[i];

		while(tmp!=NULL)
		{
			tmp2=tmp->next;
			delete tmp;
			tmp=tmp2;
		}
	}
}

void dfs(int cur,int curdepth,bool& flag,int& cost,int& save)
{
	bool retflag;
	bool childflag;
	int retcost;
	int retsave;
	int childcost;
	int childsave;
	Node* child;

	retcost=0;
	retsave=0;
	childcost=0;
	childsave=0;
	retflag=false;
	
	if(tar.find(cur)!=tar.end())
		retflag=true;

	child=map[cur];
	while(child!=NULL)
	{
		if(vis[child->num])
		{
			child=child->next;
			continue;
		}

		vis[child->num]=true;
		childflag=false;
		dfs(child->num,curdepth+child->dist,childflag,childcost,childsave);
		
		if(childflag)
		{
			retflag=true;
			
			retcost+=child->dist;
			retcost+=childcost;
				
			if(retsave<childsave)
				retsave=childsave;
		}
		
		child=child->next;
	}
	
	if(retsave==0)
	{
		if(tar.find(cur)!=tar.end())
			retsave=curdepth;
	}

	flag=retflag;
	cost=retcost;
	save=retsave;
}

int main()
{
	int i,j;
	int a,b,d;
	int cost,save,ans;
	bool flag;

	cin>>n>>start;
	memset(map,NULL,sizeof(map));
	memset(vis,false,sizeof(vis));
	tar.clear();

	for(i=1;i<n;i++)
	{
		cin>>a>>b>>d;
		Insert(a,b,d);
		Insert(b,a,d);
	}

	cin>>k;

	for(i=1;i<=k;i++)
	{
		cin>>j;
		tar.insert(j);
	}
	

	cost=0;
	save=0;
	vis[start]=true;
	dfs(start,0,flag,cost,save);
	ans=2*cost-save;
	
	cout<<ans<<endl;

	DelMap();

	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator