题意：给定一个无向图，要求构造一棵以1为根的树T，使得花费和最小。
边权(花费)：S（边的price*S(边子孙节点的weight))，可以转化为S（第个点的weight*S(该点到源点每条边上的price))
即所求为：ans = Sdist[i] * weight[i]。因weight[i]是确定的，故原题转化为求最短路问题。
因题目数目较大，故用Dijkstra+heap优化。
1
#include<iostream>
2#include<queue>
3#include<limits>
4#include<vector>
5
6using namespace std;
7
8typedef unsigned long long u64_T;
9
10const int maxN = 50001;
11const int maxM = 100010;
12const u64_T INF = numeric_limits<u64_T>::max();
13
14//边结构
15struct Edge
16
{
17
int e;
18 u64_T p;
19 Edge *next;
20
};
21
22//节点结构
23struct Node
24{
25 int v;
26 u64_T len;
27
28 bool operator < (const Node &node) const
29
{
30 return len < node.len;
31
}
32};
33
34Edge *G[maxN];
35u64_T weight[maxN];
36
37int mSet;
38
39//输入时，加边
40void addEdge(int u, int v, u64_T w)
41{
42 Edge *ptr = new Edge;
43 ptr->e = v;
44 ptr->p = w;
45 ptr->next = G[u];
46 G[u] = ptr;
47}
48
49//Dijkstra算法求最短路
50u64_T Dijkstra(int n,int s)
51{
52 priority_queue<Node> q;
53 u64_T dist[maxN];
54 Node cur,nex;
55
56 for(int i = 1;i <= n;i++)
57 {
58 dist[i] = INF;
59 }
60 dist[s] = 0;
61 cur.v = s;
62 cur.len = 0;
63 q.push(cur);
64
65 while(!q.empty())
66 {
67 cur = q.top();
68 q.pop();
69
70 if( cur.len == dist[cur.v] )
71 {
72 for(Edge* ptr = G[cur.v]; ptr != NULL; ptr = ptr->next)
73 {
74 u64_T newDist = dist[cur.v] + ptr->p;
75 if( newDist < dist[ptr->e] )
76 {
77 dist[ptr->e] = newDist;
78 nex.v = ptr->e;
79 nex.len = newDist;
80 q.push(nex);
81 }
82 }
83 }
84 }
85 for(int i = 1;i <= n; i++)
86 {
87 if(dist[i] == INF)
88 {
89 return INF;
90 }
91 }
92
93 u64_T ans = 0;
94 for(int i = 1;i <= n; i++)
95 {
96 ans += dist[i] * weight[i];
97 }
98 return ans;
99}
100
101int main()
102{
103 int T;
104 int v,e;
105 int a,b;
106 u64_T c;
107
108 int i;
109
110 scanf("%d",&T);
111 while(T--)
112 {
113 scanf("%d%d",&v,&e);
114
115 mSet = 0;
116
117 for(i=1;i<=v;i++)
118 {
119 scanf("%I64u",&weight[i]);
120 G[i] = NULL;
121 }
122 for(i=0;i<e;i++)
123 {
124 scanf("%d%d%I64u",&a,&b,&c);
125 addEdge(a,b,c);
126 addEdge(b,a,c);
127 }
128
129 u64_T ans = Dijkstra(v,1);
130
131 if(ans == INF)
132 {
133 printf("No Answer\n");
134 }
135 else
136 {
137 printf("%I64u\n",ans);
138 }
139 }
140 return 0;
141}
142