A2423 | 买礼物
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
又到了一年一度的明明生日了，明明想要买 $B$ 样东西，巧的是，这 $B$ 样东西价格都是 $A$ 元。
但是，商店老板说最近有促销活动，也就是：
如果你买了第 $I$ 样东西，再买第 $J$ 样，那么就可以只花 $K_{I,J}$ 元，更巧的是，$K_{I,J}$ 竟然等于 $K_{J,I}$。
现在明明想知道，他最少要花多少钱。
但是，商店老板说最近有促销活动，也就是：
如果你买了第 $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$。
接下来 $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
样例 $2$ 解释
先买第 $2$ 样东西，花费 $3$ 元，接下来因为优惠，买 $1,3$ 样都只要 $2$ 元，共 $7$ 元。
（同时满足多个“优惠”的时候，聪明的明明当然不会选择用 $4$ 元买剩下那件，而选择用 $2$ 元。）
数据规模
对于 $30\%$ 的数据，$1\le B\le 10$。
对于 $100\%$ 的数据，$1\le B\le500,0\le A,K_{I,J}\le1000$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？