| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
我的代码TLE了,谁能给点提示啊#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator