{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"农夫约翰当选为镇上的市长!他的竞选承诺之一是要为该地区的所有农场提供互联网连接。当然,他需要你的帮助。\n\u003cbr\u003e约翰农夫为自己的农场订购了高速连接,并打算与其他农场共享连接。为了最大程度地减少成本,他希望铺设最少量的光纤将自己的农场与所有其他农场连接起来。\n\u003cbr\u003e给定连接每对农场所需光纤的清单,你必须找到将它们全部连接在一起所需的最小光纤量。每个农场必须连接到另一个农场,以便数据包能够从任何一个农场流向任何其他农场。\n\u003cbr\u003e任意两个农场之间的距离不会超过100,000。"}},{"title":"输入","value":{"format":"HTML","content":"输入包括几个案例。对于每个案例,第一行包含农场的数量 N (3 \u003c\u003d N \u003c\u003d 100)。接下来的行包含 N x N 的连接矩阵,其中每个元素显示从一个农场到另一个农场的距离。从逻辑上讲,它们是 N 行 N 个以空格分隔的整数。从物理上讲,它们的长度限制为 80 个字符,因此有些行会延续到其他行。当然,对角线上的距离将为 0,因为对于这个问题来说,从农场 i 到它自己的距离是无趣的。"}},{"title":"输出","value":{"format":"HTML","content":"对于每个案例,输出一个单独的整数长度,即连接整组农场所需的最小光纤长度之和。"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n0 4 9 21\r\n4 0 8 17\r\n9 8 0 16\r\n21 17 16 0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e28\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}