题意：找一棵树使得造价最少，造价为每个点的子节点造价和*边的造价和
分析：最短路跑出1根节点到每个点的最短边权值，然后每个点的权值*最短边距和就是答案，注意INF开足够大，n<=1特判。Dijkstra 和 SPFA都行
代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
using namespace std; typedef long long ll;
const int N = 5e4 + 10;
const ll INF = (1ll << 16) * 50000;
struct Edge {
int v, w, nex;
Edge (int _v = 0, int _w = 0) : v (_v), w (_w) {}
bool operator < (const Edge &r) const {
return w > r.w;
}
}edge[N*2];
ll d[N];
bool vis[N];
int head[N];
int c[N];
int cnt[N];
int n, m, e; void init(void) {
memset (head, -1, sizeof (head));
e = 0;
} bool SPFA(int s) {
queue<int> Q;
memset (vis, false, sizeof (vis));
memset (cnt, 0, sizeof (cnt));
d[s] = 0; cnt[s] = 1; vis[s] = true;
Q.push (s);
while (!Q.empty ()) {
int u = Q.front (); Q.pop ();
vis[u] = false;
for (int i=head[u]; ~i; i=edge[i].nex) {
int v = edge[i].v, w = edge[i].w;
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
if (!vis[v]) {
vis[v] = true; Q.push (v);
if (++cnt[v] > n) return true;
}
}
}
}
return false;
} void Dijkstra(int s) {
priority_queue<Edge> Q;
memset (vis, false, sizeof (vis));
d[s] = 0; Q.push (Edge (s, 0));
while (!Q.empty ()) {
int u = Q.top ().v; Q.pop ();
vis[u] = true;
for (int i=head[u]; ~i; i=edge[i].nex) {
int v = edge[i].v, w = edge[i].w;
if (!vis[v] && d[v] > d[u] + w) {
d[v] = d[u] + w; Q.push (Edge (v, d[v]));
}
}
}
} void add_edge(int u, int v, int w) {
edge[e].v = v, edge[e].w = w;
edge[e].nex = head[u]; head[u] = e++;
} int main(void) {
int T; scanf ("%d", &T);
while (T--) {
scanf ("%d%d", &n, &m);
for (int i=1; i<=n; ++i) {
scanf ("%d", &c[i]); d[i] = INF;
}
init ();
for (int u, v, w, i=1; i<=m; ++i) {
scanf ("%d%d%d", &u, &v, &w);
add_edge (u, v, w); add_edge (v, u, w);
}
if (n <= 1) {
puts ("0"); continue;
}
Dijkstra (1);
// bool flag = SPFA (1);
// if (flag) {
// puts ("No Answer"); continue;
// }
ll ans = 0;
for (int i=1; i<=n; ++i) {
if (d[i] == INF) {
ans = -1; break;
}
ans += d[i] * c[i];
}
if (ans == -1) puts ("No Answer");
else printf ("%I64d\n", ans);
} return 0;
}