题意：
（这题明显感觉自己是英语渣）
给n个点从1到n标号，下面一行是每个点的权，另外给出m条边，下面是每条边的信息，两个端点+权值，边是无向边。你的任务是选出一些边，使这个图变成一棵树。这棵树的花费是这样算的，1号固定为树根，树中每个双亲节点下面的边都有个单价（即边权），然后单价乘上这条边的下面所有的子孙后代的点权和(COPY FROM:http://www.cnblogs.com/scau20110726/archive/2013/05/06/3063401.html)
思路：
题目说每个点都要用上，这时候画个图，想想乘法分配率...
坑点：
这道题的dis默认的inf值要稍大一些...
#include<stdio.h> #include<string.h> #include<queue> using namespace std; int n,m; int tmp[50005]; const long long inf=199999999999999; long long dis[50005]; bool vis[50005]; struct edge { int id; int mint; edge *next; }; edge edges[100500]; edge *adj[50005]; int ednum; inline void addEdge(int a,int b,int c) { edge *tmp; tmp=&edges[ednum]; ednum++; tmp->id=b; tmp->mint=c; tmp->next=adj[a]; adj[a]=tmp; } bool SPFA() { memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) { dis[i]=inf; } queue<int>q; q.push(1); vis[1]=1; dis[1]=0; while(!q.empty()) { int tmp=q.front(); q.pop(); vis[tmp]=0; for(edge *p=adj[tmp];p;p=p->next) { if(p->mint+dis[tmp]<dis[p->id]) { dis[p->id]=p->mint+dis[tmp]; if(!vis[p->id]) { q.push(p->id); vis[p->id]=1; } } } } for(int i=1;i<=n;i++) { if(dis[i]==inf) return 0; } return 1; } long long cal() { long long rel=0; for(int i=1;i<=n;i++) { rel+=((long long )dis[i])*tmp[i]; } return rel; } int main() { int t,a,b,c; scanf("%d",&t); for(int tt=1;tt<=t;tt++) { ednum=0; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { adj[i]=NULL; } for(int i=1;i<=n;i++) { scanf("%d",&tmp[i]); } for(int i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&c); addEdge(a,b,c); addEdge(b,a,c); } if(SPFA()) { printf("%I64d ",cal()); } else { printf("No Answer "); } } }