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