#P3013. Big Christmas Tree
Big Christmas Tree
题目描述
圣诞节即将来到KCM市。KCM市的忠实市民Suby正在准备一棵漂亮的大圣诞树。这棵树的基本结构如右图所示。
这棵树可以表示为由编号节点和若干边组成的集合。节点编号为到,根节点始终为。树中每个节点都有其权重,各节点的权重可能不同。此外,每两个节点之间可用的边的形状也不同,因此每条边的单位价格也不同。由于技术限制,每条边的价格将等于(该边所有后代节点的权重之和)×(该边的单位价格)。
Suby希望在所有可能的选择中使整棵树的总成本最小。同时他希望使用所有节点,因为他想要一棵大树。因此他决定请你帮忙解决这个问题,找出最小成本。
输入格式
输入包含个测试用例。第一行输入测试用例数量。每个测试用例包含若干行:
- 第一行给出两个数字、(),分别表示节点数量和可用边数量。
- 第二行给出个正整数,表示个节点的权重。
- 接下来的行,每行包含三个正整数、、,表示可以连接节点和的边,其单位价格为。
输入中的所有数字均小于。
输出格式
对于每个测试用例,输出一个整数表示该树的最小可能成本。如果无法构建圣诞树,则输出一行"No Answer"。
输入样例 1
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
输出样例 1
15
1210
题目来源
POJ Monthly--2006.09.29, Kim, Chan Min (kcm1700@POJ)