Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
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: