P1546 [USACO3.1] Shortest Network Agri-Net

Farmer John has been elected mayor of their town! One of his campaign promises is to bring the Internet to the town and connect all the farms. Of course, he needs your help.

FJ has arranged a high-speed network line for his farm, and he wants to share it with other farms. To minimize the cost, he wants to lay the shortest optical fiber to connect all the farms. You are given a list of connection costs between farms. You must find a plan that connects all farms with the minimum total fiber length. The distance between any two farms will not exceed $10^5$.

The first line contains the number of farms $N$ ($3 \leq N \leq 100$). Next is an $N \times N$ matrix representing the distance between each pair of farms. In theory, it consists of $N$ lines, each with $N$ integers separated by spaces. In practice, due to the $80$-character-per-line limit, some rows may continue directly onto subsequent lines. The diagonal entries are $0$, since there is no line from the $i$-th farm to itself.

Output a single integer: the minimum total length of fiber needed to connect all farms.

Problem translation from NOCOW. USACO Training Section 3.1. Translated by ChatGPT 5