{"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"}}]}