计蒜客圣诞树问题：最小价值树构造

问题描述

圣诞节快到了，蒜头君准备做一棵大 圣诞树 。
这棵树被表示成一组被编号的结点和一些边的集合，树的结点从 1 到 n 编号，树的根永远是 1。每个结点都有一个自身特有的数值，称为它的 权重 ，各个结点的权重可能不同。对于一棵做完的树来说，每条边都有一个价值 ve，若设这条边 e 连接结点 i 和结点 j，且 i 为 j的父结点（根是最老的祖先），则该边的价值ve=sj*we,sj表示结点 j 的所有子孙及它自己的权重之和，we表示边 e 的权值。
现在蒜头君想造一棵树，他有 m 条边可以选择，使得树上所有边的总价值最小，并且所有的点都在树上，因为蒜头君喜欢大树。
输入格式
第一行输入两个整数 n 和 m(0≤n,m≤50,000），表示结点总数和可供选择的边数。
接下来输入一行，输入 n 个整数，依次表示每个结点的权重。
接下来输入 m 行，每行输入 3 个正整数a,b,c（1≤a,b,≤n,1≤c≤10,000），表示结点 a 和结点 b 之间有一条权值为 c 的边可供造树选择。
输出格式
输出一行，如果构造不出这样的树，请输出No Answer，否则输出一个整数，表示造树的最小价值。
样例输入
4 4
10 20 30 40
1 2 3
2 3 2
1 3 5
2 4 1
样例输出
370

A C代码 (NOIP的Dev-C++过不了版）

#include<iostream> #include<cstdio> #include<algorithm> #include<set> #include<vector> #include<cstring> using namespace std; const int maxn=50007; struct edge{ int v,w,nxt; }e[maxn<<1]; //邻接表要开两倍 int p[maxn],n,m,eid,dist[maxn],r[maxn]; bool vst[maxn]; void init(){ memset(p,-1,sizeof(p)); eid=0; } typedef pair<int,int> PII; set<PII,less<PII> > min_heap;

相关知识

圣诞树是什么树？圣诞树摆放位置？
新西兰圣诞树 花卉观赏 顺口溜二首
圣诞树背后的故事：生物学家花了40年时间，只为通过基因工程培育完美圣诞树
圣诞树背后的故事：生物学家花了40年时间，只为通过基因工程培育完美圣诞树...
圣诞树背后的故事：生物学家花了40年时间，只为用基因测序培育完美圣诞树
圣诞树由来 圣诞树原本是什么树
圣诞树如何装饰,圣诞树的由来,圣诞树是什么树,圣诞树价格
圣诞树是什么树
圣诞树是什么树？在家如何装饰出精美的圣诞树？
圣诞树是什么树，象征什么

网址: 计蒜客圣诞树问题：最小价值树构造 https://www.huajiangbk.com/newsview2592534.html