学步园

http://acm.bupt.edu.cn/onlinejudge/newoj/ShowContest/show_contest_problem.php?contest_id=140&problem_id=196&problem_rank=A

我用的是记忆化搜索来实现树状DP。

首先以点1为根进行建树。然后dp[i][0],dp[i][1] 记录的是以i为根的，到其子树的叶子结点的两个最小的距离

注意i有0个或1个子树的情况，还要注意1这个根节点的子树情况。

最后搜索一遍dp[i][0]+dp[i][1],取最小值。

1Y，可是发现时间并不是很快，500多ms。可能是我用了vector的原因，还是什么情况？

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string.h>
#include <vector>
using namespace std;

const int maxn = 10005;
const int maxint = 2147483647;
struct Info
{
	int v;
	int d;
};

vector<Info>v[maxn];
vector<Info>vv[maxn];
int vis[maxn];
int dp[maxn][2];
int n,mins;

void dfs(int u)
{
   vis[u]=true;
   for(int i=0;i<(int)v[u].size();i++)
   {
       if(!vis[v[u][i].v])
	   {
           Info tmp;
		   tmp.v=v[u][i].v;
		   tmp.d=v[u][i].d;
		   vv[u].push_back(tmp);
		   dfs(v[u][i].v);
	   }
   }
}

int Cal_dp(int u)
{
	if(vv[u].size()==0)
		return 0;
    for(int i=0;i<(int)vv[u].size();i++)
	{
		int t=Cal_dp(vv[u][i].v);
		if(t+vv[u][i].d<dp[u][1])
			dp[u][1]=t+vv[u][i].d;
		if(dp[u][0]>dp[u][1])
			swap(dp[u][0],dp[u][1]);
	}
	return dp[u][0];
}

int main()
{
	int a,b,c;
	Info tmp;
    while(scanf("%d",&n) && n!=0)
	{
		for(int i=1;i<=n;i++)
		{
			v[i].clear();
			vv[i].clear();
		}

		for(int i=1;i<=n-1;i++)
		{
			scanf("%d %d %d",&a,&b,&c);
			tmp.v=b;
			tmp.d=c;
			v[a].push_back(tmp);
			tmp.v=a;
			tmp.d=c;
			v[b].push_back(tmp);
		}
		memset(vis,false,sizeof(vis));
		dfs(1);
		for(int i=1;i<=n;i++)
		{
			if(vv[i].size()==0)
				dp[i][0]=0,dp[i][1]=0;
			else
			    dp[i][0]=maxint,dp[i][1]=maxint;
		}
		if(n==2)
		{
			printf("%d\n",vv[1][0].d);
			continue;
		}
        for(int i=0;i<(int)vv[1].size();i++)
		{
           int t=Cal_dp(vv[1][i].v);
           if(t+vv[1][i].d<dp[1][1])
			   dp[1][1]=t+vv[1][i].d;
		   if(dp[1][1]<dp[1][0])
			   swap(dp[1][1],dp[1][0]);
		}

		int mins = maxint;
		if(vv[1].size()==1)
		{
			if(dp[1][0]<mins)
				mins=dp[1][0];
		}

		for(int i=1;i<=n;i++)
		{
            if(vv[i].size()==0 || vv[i].size()==1)
                continue;
			if(dp[i][0]+dp[i][1]<mins)
				mins=dp[i][0]+dp[i][1];
		}
		printf("%d\n",mins);
	}
	return 0;
}