题意：
有一张有权无向图，编号1的点为根，要求一个生成树，使得总花费sum(每条边的花费×子树所有节点花费的和)最小，输出这个值。
分析：
自己想了半天，永远离不开生成树上面，因为之前知道这个题是用最短路做的，想了半天也想不通为什么会是用最大路做的。
如果放在现场，自己肯定做不出来。
其实这题主要的思想转化在于sum(每条边的花费×子树所有节点花费的和)这个公式。
这个公式其实是等价于sum(每条点的花费×该点到根的边花费的和)。
稍微想想就能明白了。
其他的已经没什么难度了，无非是最短路而已。
不过这题有坑，按道理n==0应该是输出No Answer。
因为：
不过也发现自己的思维真的很江化，算了，慢慢来。
脑子不够就用经验凑。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <queue> 5 #include <vector> 6 7 8 using namespace std; 9 10 typedef long long ll; 11 const ll inf = 1ll<<60; 12 const int maxn=50010; 13 14 15 int t; 16 int n,m; 17 ll pa[maxn]; 18 19 struct Edge { 20 int v; 21 ll c; 22 }; 23 24 struct Node { 25 int v; 26 ll c; 27 Node(int _v,ll _c) { 28 v=_v,c=_c; 29 } 30 bool operator<(const Node &a)const { 31 return c>a.c; 32 } 33 }; 34 35 36 vector<Edge> edge[maxn]; 37 bool vis[maxn]; 38 ll dist[maxn]; 39 40 bool dijkstra(int n,int s) { 41 memset(vis,false,sizeof(vis)); 42 for(int i=1; i<=n; i++)dist[i]=inf; 43 priority_queue<Node> pq; 44 while(!pq.empty())pq.pop(); 45 dist[s]=0; 46 pq.push(Node(s,0)); 47 int cnt=0; 48 while(!pq.empty()) { 49 Node tmp = pq.top(); 50 pq.pop(); 51 int u=tmp.v; 52 if(vis[u])continue; 53 cnt++; 54 vis[u]=true; 55 for(int i=0; i<edge[u].size(); i++) { 56 int v = edge[u][i].v; 57 ll c = edge[u][i].c; 58 if(!vis[v]&&dist[v]>dist[u]+c) { 59 dist[v]=dist[u]+c; 60 pq.push(Node(v,dist[v])); 61 } 62 } 63 } 64 return cnt>=n; 65 } 66 67 int main() { 68 scanf("%d",&t); 69 while(t--) { 70 for(int i=0; i<=n; i++) { 71 edge[i].clear(); 72 } 73 scanf("%d%d",&n,&m); 74 for(int i=1; i<=n; i++) { 75 scanf("%lld",&pa[i]); 76 } 77 for(int i=0; i<m; i++) { 78 int u,v; 79 ll c; 80 scanf("%d%d%lld",&u,&v,&c); 81 edge[u].push_back(Edge{v,c}); 82 edge[v].push_back(Edge{u,c}); 83 } 84 if(n<=1) { 85 puts("0"); 86 continue; 87 } 88 if(dijkstra(n,1)) { 89 ll ans=0; 90 for(int i=2; i<=n; i++) { 91 ans+=dist[i]*pa[i]; 92 } 93 printf("%lld\n",ans); 94 } else { 95 puts("No Answer"); 96 } 97 98 } 99 100 101 return 0; 102 103 }