{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003ch2 align\u003d\"center\"\u003eSunny Cup 2003 - Preliminary Round\u003c/h2\u003e\n\u003cp align\u003d\"center\"\u003e4月20日,12:00 - 17:00 \u003c/p\u003e\n\u003ch3 align\u003d\"center\"\u003e问题 E: QS 网络\u003c/h3\u003e\n\u003cp\u003e\u003cbr\u003e\n 在银河系 cgb 的 w-503 行星上,有一种名为 QS 的智能生物。QS 通过网络相互通信。如果两个 QS 想要连接,它们需要购买两个网络适配器(每个 QS 一个),以及一段网络电缆。请注意,一个网络适配器只能用于单个连接。(即,如果一个 QS 想要建立四个连接,它需要购买四个适配器)。在通信过程中,一个 QS 将其消息广播给所有与其连接的 QS,接收到消息的 QS 组将消息广播给所有与其连接的 QS,该过程重复,直到所有的 QS 都接收到消息。\u003c/p\u003e\n\u003cp\u003e以下是一个示例:\u003c/p\u003e\n\u003cp align\u003d\"center\"\u003e\u003cimg src\u003d\"CDN_BASE_URL/1120637f03c5c4bc9402775a6100caa8?v\u003d1710692868\" width\u003d\"232\" height\u003d\"197\"\u003e\u003c/p\u003e\n\u003cp\u003e\u003c/p\u003e\n\u003cp\u003e\u003cbr\u003e\n 一个示例 QS 网络,QS A 想要发送一条消息。\u003cbr\u003e\n \u003cbr\u003e\n 步骤 1. QS A 将消息发送给 QS B 和 QS C;\u003cbr\u003e\n \u003cbr\u003e\n 步骤 2. QS B 将消息发送给 QS A;QS C 将消息发送给 QS A 和 QS D;\u003cbr\u003e\n \u003cbr\u003e\n 步骤 3. 过程终止,因为所有的 QS 都接收到了消息。\u003c/p\u003e\n\u003cp\u003e 每个 QS 都有自己喜欢的网络适配器品牌,并且总是在所有连接中购买该品牌。此外,QS 之间的距离是不同的。给定每个 QS 喜欢的网络适配器的价格以及每对 QS 之间电缆的价格,你的任务是编写一个程序来确定建立 QS 网络的最小成本。\u003c/p\u003e\n\u003cp\u003e\u003cbr\u003e\n \u003cb\u003e输入\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e输入的第一行包含一个整数 t,表示数据集的数量。\u003cbr\u003e\n \u003cbr\u003e\n 从第二行开始,有 t 个数据集。\u003cbr\u003e\n \u003cbr\u003e\n 在单个数据集中,第一行包含一个整数 n,表示 QS 的数量。\u003cbr\u003e\n \u003cbr\u003e\n 第二行包含 n 个整数,表示每个 QS 喜欢的网络适配器的价格。\u003cbr\u003e\n \u003cbr\u003e\n 在第三行到第 n+2 行之间包含一个矩阵,表示每对 QS 之间电缆的价格。\u003c/p\u003e\n\u003cp\u003e约束条件:\u003c/p\u003e\n\u003cp\u003e输入中的所有整数均为非负且不超过 1000。\u003c/p\u003e\n\u003cp\u003e\u003c/p\u003e\n\u003cp\u003e\u003cbr\u003e\n \u003cb\u003e输出\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e对于每个数据集,输出最小成本在一行中。不需要额外的空行。\u003c/p\u003e\n\u003cp\u003e\u003cbr\u003e\n \u003cb\u003e示例输入\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e1\u003cbr\u003e\n 3\u003cbr\u003e\n 10 20 30\u003cbr\u003e\n 0 100 200\u003cbr\u003e\n 100 0 300\u003cbr\u003e\n 200 300 0\u003c/p\u003e\n\u003cp\u003e\u003cbr\u003e\n \u003cb\u003e示例输出\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e370\u003cbr\u003e\n\u003c/p\u003e\n\u003cp\u003e\u003cbr\u003e\n\u003c/p\u003e"}}]}