题目：http://poj.org/problem?id=3013
看似生成树，实则最短路，可以将题意转化为点权*根到此点的边权和(最短路使其最小)。
代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; typedef long long ll; queue<int>q; int t,n,m,head[50005],ct,s[50005]; bool in[50005]; ll dis[50005],INF=1e10,ans; struct N{ int to,next,w; N(int t=0,int n=0,int ww=0):to(t),next(n),w(ww) {} }edge[100005]; int main() { scanf("%d",&t); while(t--) { ct=0; memset(head,0,sizeof head); memset(in,0,sizeof in); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&s[i]),dis[i]=INF; for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); edge[++ct]=N(y,head[x],z);head[x]=ct; edge[++ct]=N(x,head[y],z);head[y]=ct; } while(q.size())q.pop(); dis[1]=0;q.push(1);in[1]=1; while(q.size()) { int x=q.front();q.pop(); in[x]=0; for(int i=head[x];i;i=edge[i].next) { int u=edge[i].to; if(dis[u]>dis[x]+edge[i].w) { dis[u]=dis[x]+edge[i].w; if(!in[u])in[u]=1,q.push(u); } } } bool flag=0;ans=0; for(int i=1;i<=n;i++) { if(dis[i]==INF) { flag=1;break; } ans+=dis[i]*s[i]; } if(flag)printf("No Answer "); else printf("%lld ",ans); } return 0; }