题目描述：给你一些点和边，都有权值。这里，边的权值叫做权值1.

第一个点是树根。

当用一部分给定的边构成一棵树时，每条边的实际权值（权值2）等于（它所连的所有子节点的权值和 * 这条边开始给定的权值）

问构成一棵树的最小的 权值2 是多少。

解题报告：

自己随便建一棵树，把求解的式子列出来，就很容易发现：

从根节点到其他节点i的消耗是：经过边的权值1的和 * i节点的权值。

那么。就转化成了：按照权值1建图，求根节点到其他节点的最短路，每条最短路再乘以那个点的权值，最后求和就是答案。

问题在于：点和边都可能有50000之多，n^2算法肯定不行，因此可用的是：

spfa 和 Dij + heap

最好都不要用stl，这题卡时间。

代码如下：700msAC

#include<iostream>
using namespace std;
#define SIZE 50010
struct edge{int to, value, next;}y[SIZE * 2];
int t, v, e, x[SIZE], from, to, va, que[SIZE * 10], vst[SIZE], id;
int sta[SIZE], cnt;
long long d[SIZE];
void spfa()
{
    memset(vst, 0, sizeof(vst));
    memset(d, -1, sizeof(d));
    d[1] = 0;
    int head = 0, tail = 0;
    que[tail++] = 1;vst[1] = 1;
    while(head != tail)
    {
        from = que[head], id = sta[que[head]];
        vst[from] = 0;
        head++;
        while(id != -1)
        {
            to = y[id].to;
            if (d[to] == -1 || d[from] + y[id].value < d[to])
            {
                d[to] = d[from] + y[id].value;
                if (!vst[to])
                {
                    vst[to] = 1;
                    que[tail++] = to;
                }
            }
            id = y[id].next;
        }
    }
    long long ans = 0;
    for(int i = 1; i <= v; i++)
    {
        if (d[i] == -1)
        {
            printf("No Answer\n");
            return;
        }
        ans += d[i] * x[i];
    }
    printf("%I64d\n", ans);
}
void insert(int from, int to, int va)
{
    y[cnt].to = to; y[cnt].value = va; y[cnt].next = sta[from];
    sta[from] = cnt++;
}
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &v, &e);
        memset(sta, -1, sizeof(sta)); cnt = 0;
        for(int i = 1; i <= v; i++) scanf("%d", &x[i]);
        for(int i = 0; i < e; i++)
        {
            scanf("%d%d%d", &from, &to, &va);
            insert(from, to, va); insert(to, from, va);
        }
        spfa();
    }
    return 0;
}