求图上根为1的生成树使得各边权*子树点权和最小。
光看这个式子并没有卵用。专门迷惑人的233。
考虑每个点对答案的贡献，即该点的点权*其祖先边权和。
即上式等价于
要使总答案最小，即让各点祖先边权和都尽可能地少，而祖先边权和即该点到根节点的距离，祖先边权和的最小值就是该点到根节点的最短距离。
因此从根节点跑一次Dij即可。
我有点方，一个劲TLE不知道什么鬼，然后眼睛就看到最后退出循环的i=2147483647，发现for i+1以后i=-2147483648。。。于是死循环了。。。
#include <cstdio>
#include <cstring>
#include <queue>
#define FOR(i,j,k) for(i=j;i<=k;i++)
using namespace std;
const int N = 100001, M = 100001;
int h[N], p[M], v[M], w[M], f[N], cnt, vis[N];
long long dis[N];
struct Data { int x, c; };
bool operator <(Data a, Data b){ return a.c > b.c; }
void add(int x, int y, int z) {
p[++cnt] = h[x]; w[cnt] = z; v[cnt] = y; h[x] = cnt;
}
void dij() {
priority_queue<Data> q;
memset(dis, 127, sizeof dis);
memset(vis, 0, sizeof vis);
dis[1] = 0;
q.push((Data) {1, 0});
while (!q.empty()) {
Data u = q.top(); q.pop();
if (vis[u.x]) continue;
vis[u.x] = 1;
for (int i = h[u.x]; i; i = p[i])
if (!vis[v[i]] && dis[v[i]] > dis[u.x] + w[i]) {
dis[v[i]] = dis[u.x] + w[i];
q.push((Data) {v[i], dis[v[i]]});
}
}
}
int main() {
int n, i, m, q, t, a, b, c;
scanf("%d", &t);
while (t--) {
cnt = 0;
memset(h, 0, sizeof h);
scanf("%d%d", &n, &m);
FOR(i,1,n) scanf("%d", f + i);
while (m--) {
scanf("%d%d%d", &a, &b, &c);
add(a, b, c); add(b, a, c);
}
dij();
long long ans = 0;
FOR(i,1,n)
if (dis[i] == 0x7f7f7f7f7f7f7f7fll) i = 2147483645;
else ans += dis[i] * f[i];
if (i == 2147483646) puts("No Answer");
else printf("%lld\n", ans);
}
return 0;
}Big Christmas Tree
Time Limit: 3000MS Memory Limit: 131072K
Total Submissions: 22439 Accepted: 4867
Description
Christmas is coming to KCM city. Suby the loyal civilian in KCM city is preparing a big neat Christmas tree. The simple structure of the tree is shown in right picture.
The tree can be represented as a collection of numbered nodes and some edges. The nodes are numbered 1 through n. The root is always numbered 1. Every node in the tree has its weight. The weights can be different from each other. Also the shape of every available edge between two nodes is different, so the unit price of each edge is different. Because of a technical difficulty, price of an edge will be (sum of weights of all descendant nodes) × (unit price of the edge).
Suby wants to minimize the cost of whole tree among all possible choices. Also he wants to use all nodes because he wants a large tree. So he decided to ask you for helping solve this task by find the minimum cost.
Input
The input consists of T test cases. The number of test cases T is given in the first line of the input file. Each test case consists of several lines. Two numbers v, e (0 ≤ v, e ≤ 50000) are given in the first line of each test case. On the next line, v positive integers wi indicating the weights of v nodes are given in one line. On the following e lines, each line contain three positive integers a, b, c indicating the edge which is able to connect two nodes a and b, and unit price c.
All numbers in input are less than 216.
Output
For each test case, output an integer indicating the minimum possible cost for the tree in one line. If there is no way to build a Christmas tree, print “No Answer” in one line.
Sample Input
2
2 1
1 1
1 2 15
7 7
200 10 20 30 40 50 60
1 2 1
2 3 3
2 4 2
3 5 4
3 7 2
3 6 3
1 5 9
Sample Output
15
1210