题意：找一棵树使得造价最少，造价为每个点的子节点造价和*边的造价和
分析：最短路跑出1根节点到每个点的最短边权值，然后每个点的权值*最短边距和就是答案，注意INF开足够大，n<=1特判。Dijkstra 和 SPFA都行
代码：
#include#include #include #include #include #include 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 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 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;}