题意：

圣诞树是一颗无向树形图，其中，编号为1的节点为根节点，原始图中每条边具有边权（unit）：材料的单位价值，

每个点也有一个权(weight)：点的重量。生成树中，各个点处的花费是指向该点的边权（unit）* 该点的子树中所有点的重量（weight）和，

总的花费则是生成树中所有点的花费之和。

思路：

1. 关键是把题目转换成单源最短路径，每个点所产生的消耗为：该点的权值 * 根节点到该点的距离;

2. SPFA 求单源最短路径，输出结果为 1 中的累加。 

 

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int MAXN = 50010;const __int64 INFS = 0x3FFFFFFF7FFFFFFF;struct edge {
         int v;    __int64 cost;    edge* next;} *V[MAXN], ES[MAXN*2];int EC;__int64 d[MAXN], weight[MAXN];bool inq[MAXN];void addedge(int u, int v, int cost) {
         ES[++EC].next = V[u];     V[u] = ES + EC;    V[u]->v = v, V[u]->cost = cost;}void SPFA(int s, int n) {
         for (int i = 1; i <= n; i++)        d[i] = INFS, inq[i] = false;    queue
        
          Q;    Q.push(s);    d[s] = 0, inq[s] = true;    while (!Q.empty()) {
             int u = Q.front(); Q.pop();        inq[u] = false;        for (edge* e = V[u]; e; e = e->next) {
                 if (d[e->v] > d[u] + e->cost) {
                     d[e->v] = d[u] + e->cost;                if (!inq[e->v]) {
                          inq[e->v] = true; Q.push(e->v);                 }            }        }    }}int main() {
         int cases;    scanf("%d", &cases);    while (cases--) {
             int n, e;        scanf("%d%d", &n, &e);        for (int i = 1; i <= n; i++) {
                 scanf("%I64d", &weight[i]);            V[i] = 0;        }        EC = 0;        for (int i = 0; i < e; i++) {
                 int u, v;            __int64 cost;            scanf("%d%d%I64d", &u, &v, &cost);            addedge(u, v, cost);            addedge(v, u, cost);        }        SPFA(1, n);        __int64 ans = 0;        bool flag = false;        for (int i = 1; i <= n; i++) {
                 ans += weight[i] * d[i];            if (d[i] == INFS) {
                     flag = true; break;            }        }        if (flag)             printf("No Answer\n");        else             printf("%I64d\n", ans);    }    return 0;}