问题4280--买礼物4280: 买礼物
时间限制: 1 Sec 内存限制: 512 MB
提交: 0 解决: 0
[提交] [状态] [讨论版] [命题人:]题目描述
又到了一年一度的明明生日了，明明想要买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，那么表示这两样东西之间不会导致优惠。
输出
一个整数，为最小要花的钱数。
样例输入
(1)
1 1
0
(2)
3 3
0 2 4
2 0 2
4 2 0
样例输出
(1)
1
(2)
7
样例解释2
先买第2样东西，花费3元，接下来因为优惠，买1,3样都只要2元，共7元。
（同时满足多个“优惠”的时候，聪明的明明当然不会选择用4元买剩下那件，而选择用2元。）
来源/分类
[提交] [状态]