题目大意：给你 n 个节点，编号从1 到 n ，节点 1 为根节点，并且每个节点都有一个重量 w ，现在要在这些点之间建设公路，要求必须包含所有节点并且使整个图连通，总费用为 每条边的单价 * （该边所有子节点的重量之和） 。其实这是一个最短路的问题，经过推倒，总费用 = 每个节点的重量 * 该节点到根节点（节点1）的最短路径。
Ps：此题卡精度 ， 需用long long ， int 范围不够， double 精度不够 。
请看代码：
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<vector>
#include<queue>
#define mem(a , b) memset(a , b , sizeof(a))
using namespace std ;
const int MAXN = 5e4 + 5 ;
const long long INF = 0x7fffffffffffffff ;
long long dis[MAXN] ;
int w[MAXN] ;
struct Edge
{
int adj ;
int d ;
int next ;
} e[MAXN * 2] ;
int n , se ;
int ecnt ;
int head[MAXN] ;
bool inq[MAXN] ;
int root ;
void chu()
{
ecnt = 0 ;
mem(head , -1) ;
mem(inq , 0) ;
root = 1 ;
}
void init()
{
scanf("%d%d" , &n , &se) ;
int i ;
for(i = 1 ; i <= n ; i ++)
{
scanf("%d" , &w[i]) ;
}
for(i = 0 ; i < se ; i ++)
{
int a , b , d ;
scanf("%d%d%d" , &a , &b , &d) ;
e[ecnt].adj = b ;
e[ecnt].d = d ;
e[ecnt].next = head[a] ;
head[a] = ecnt ;
ecnt ++ ;
e[ecnt].adj = a ;
e[ecnt].d = d ;
e[ecnt].next = head[b] ;
head[b] = ecnt ;
ecnt ++ ;
}
}
queue<int> q ;
void spfa()
{
while (!q.empty()) q.pop() ;
q.push(root) ;
inq[root] = true ;
int tmp ;
while (!q.empty())
{
tmp = q.front() ;
q.pop() ;
inq[tmp] = false ;
int i ;
for(i = head[tmp] ; i != -1 ; i = e[i].next)
{
Edge t = e[i] ;
int tv ;
tv = t.adj ;
int td = t.d ;
if(dis[tmp] < INF && dis[tmp] + td < dis[tv])
{
dis[tv] = dis[tmp] + td ;
if(!inq[tv])
{
inq[tv] = true ;
q.push(tv) ;
}
}
}
}
}
void solve()
{
if(n == 0 || n == 1) {
printf("0\n") ;
return ;
}
int i ;
for(i = 1 ; i <= n ; i ++)
{
dis[i] = INF ;
}
dis[1] = 0 ;
spfa() ;
long long ans = 0 ;
for(i = 1; i <= n ; i ++)
{
if(dis[i] == INF)
{
printf("No Answer\n") ;
return ;
}
ans += w[i] * dis[i] ;
}
printf("%lld\n" , ans) ;
}
int main()
{
int T ;
scanf("%d" , &T) ;
while (T --)
{
chu() ;
init() ;
solve() ;
}
return 0 ;
}