题目描述

又到了一年一度的明明生日了，明明想要买 B 样东西，巧的是，这 B 样东西价格都是 A 元。 但是，商店老板说最近有促销活动，也就是： 如果你买了第 I 样东西，再买第 J 样，那么就可以只花 K[I,J]元，更巧的是，K[I,J]竟然等于 K[J,I]。 现在明明想知道，他最少要花多少钱。

输入格式

第一行两个整数，A,B。 接下来 B 行，每行 B 个数，第 I 行第 J 个为 K[I,J]。 我们保证 K[I,J]=K[J,I] 并且 K[I,I]=0。 特别的，如果 K[I,J]=0，那么表示这两样东西之间不会导致优惠。 注意 K[I,J] 可能大于 A。

输出格式

一个整数，为最小要花的钱数。

样例

输入样例 1

1 1
0

输出样例 1

1

输入样例 2

3 3
0 2 4
2 0 2
4 2 0

输出样例 2

7

输入样例 3

3 4
0 1 0 0
1 0 0 0
0 0 0 0
0 0 0 0

输出样例 3

10

提示

数据规模：1≤B≤500,0≤A,K[I,J] ≤1000。

样例说明：样例解释 2。 先买第 2 样东西，花费 3 元，接下来因为优惠，买 1,3 样都只要 2 元，共 7 元。 （同时满足多个“优惠”的时候，聪明的明明当然不会选择用 4 元买剩下那件，而选择用 2 元。）

思路：题意：找到购买所有商品的最小总成本（无向图的最小生成树的权值和） 建图注意点： 创建一个包含 B+1 个节点的图，节点 0 是虚拟节点，代表初始购买状态。虚拟节点到每个商品节点的边权为 A，表示直接购买该商品的成本。商品之间的边权为优惠价格和原价中的较小值，如果优惠不可用则使用原价。 使用Prim算法计算最小生成树的总权重。该算法从虚拟节点开始，逐步扩展生成树，每次选择当前生成树到未访问节点的最小边权，确保总成本最小。