学步园

JLUCPC

题目：http://acm.hdu.edu.cn/showproblem.php?pid=3899

题意：一棵树，给出每个点的权值和每条边的长度，点j到点i的代价为点j的权值乘以连接i和j的边的长度。求点x使得所有点到点x的代价最小，输出最小值。

题解：求出一个点的代价后可以进行相应的转移求出相邻点的代价。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX 100010
#define inf 0xfffff
#define LL long long
#pragma comment(linker, "/STACK:1024000000,1024000000")
//内存挂
int edge[MAX<<1];//表示第i条边的终点
int next[MAX<<1];//与第i条边同起点的下一条边的位置
int head[MAX<<1];//以i为起点的第一条边的储存位置
int cost[MAX<<1];
LL dp[MAX];
LL value[MAX];//每个结点的权值
LL dist[MAX];//子树的权值和
int cnt=0;
void insert(int a,int b,int c)//a起点,b终点
{
    edge[++cnt]=b;
    next[cnt]=head[a];
    head[a]=cnt;
    cost[cnt]=c;
}
void dfs_dist(int x,int pre,int dis)
{
    dp[1]+=(dis*value[x]);
    dist[x]=value[x];
    for(int i=head[x];i!=-1;i=next[i])
    {
        if(edge[i]==pre) continue;
        dfs_dist(edge[i],x,dis+cost[i]);
        dist[x]+=dist[edge[i]];
    }
}
void dfs(int x,int pre)
{
    for(int i=head[x];i!=-1;i=next[i])
    {
        if(edge[i]==pre) continue;
        int k=edge[i];
        dp[k]=dp[x]+(dist[1]-dist[k]-dist[k])*cost[i];
        //对于一条边，求出这条边上面所以边的长度和和下面所有边的长度和，然后就可以进行转移了
        dfs(k,x);
    }
}
int main()
{
    int n;
    int a,b,c;
    for(;~scanf("%d",&n);)
    {
        for(int i=1;i<=n;++i) scanf("%I64d",value+i);
        cnt=0;
        memset(dp,0,sizeof(dp));
        memset(dist,0,sizeof(dist));
        memset(head,-1,sizeof(head));
        memset(next,-1,sizeof(next));
        for(int i=1;i<n;++i)
        {
            scanf("%d%d%d",&a,&b,&c);
            insert(a,b,c);
            insert(b,a,c);
        }
        dfs_dist(1,-1,0);
        dfs(1,-1);
        LL ans=dp[1];
        for(int i=2;i<=n;++i) ans=min(ans,dp[i]);
        printf("%I64d\n",ans);
    }
    return 0;
}

来源：http://blog.csdn.net/acm_ted/article/details/7901420