POJ 3013

Big Christmas Tree

题目链接

解题思路

price of an edge will be (sum of weights of all descendant nodes) × (unit price of the edge).
每条边的代价为孩子节点总重量的和*边的单位代价；
通过分析可知，答案是根节点到（每个节点的最短路径*相对应节点的权重）的和；

注意的点

1. 使用scanf,printf，而不是cin,cout ，节省数据读入，显示的时间；

代码

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define N 50005
long long inf = 0x7fffffffffffffff;
long long ans[N];
int w[N];
int vis[N];
int head[N];
struct Ed{
    int to;
    int c;
    int next; 
    Ed(){}
    Ed(int a,int b):to(a),c(b){
    }
};
Ed edge[N * 2];
int etot;
void addEdge(int u,int v,int w)
{
    edge[etot].to = v;
    edge[etot].c = w;
    edge[etot].next = head[u];
    head[u] = etot++;
    
    edge[etot].to = u;
    edge[etot].c = w;
    edge[etot].next = head[v];
    head[v] = etot++; 
}
struct Nod{
    int id;
    long long c;
    Nod(){}
    Nod(int a,long long b):id(a),c(b){
    }
    bool operator < (const Nod&a)const
    {
        return c > a.c;
    }
};
int n,m;
void init()
{
    etot = 0;
    for(int i = 1; i <= N; ++i)
    {
        vis[i] = 0;
        head[i] = -1;
        ans[i] = inf;
        w[i] = 0;
    }
}
void dij(int s)
{
    Nod tmp,nowd;
    priority_queue<Nod> q;
    ans[s] = 0;
    nowd.c = 0;
    nowd.id = s;
    q.push(nowd);
    int id;
    while(!q.empty())
    {
        nowd = q.top();
        int now = nowd.id;
        q.pop();
        vis[now] = 1;
        if(nowd.c > ans[now])
        {
            continue;
        }
        long long dis;
        for(int i = head[now]; i != -1; i = edge[i].next)
        {
            id = edge[i].to;
            dis = ans[now] + edge[i].c;
            if(!vis[id] && dis < ans[id])
            {
                ans[id] = dis;
                tmp.c =dis;
                tmp.id = id;
                q.push(tmp);
            }
        } 
    }
}
int input()
{
    init();
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d",&w[i]);
        //cin >> w[i];
    }
    int u,v,c;
    for(int i = 0; i < m; ++i)
    {
        scanf("%d%d%d",&u,&v,&c);
        //cin >> u >> v >> c;
        addEdge(u,c);
    }
    dij(1);
    long long out = 0;
    for(int i = 1;i <= n; ++i)
    {
        if(ans[i] == inf)
        {
            printf("No Answern");
            return 0;
        }
        out += ans[i] * w[i];
    }
    printf("%lldn",out);
    return 0;
}
int main()
{
    int num;
    scanf("%d",&num);
    for(int i = 0; i < num; ++i)
    {
        input();
    }
    return 0;
}

如有错误，恳请指正