P1550 [USACO08OCT] Watering Hole G

Farmer John’s farm is short of water. He decides to bring water to his $n$ fields. He can dig some wells and build channels between fields to connect them for water supply. Digging a well in field $i$ costs $W_i$ units. Connecting field $i$ and field $j$ costs $P_{i,j}$ (with $P_{j,i} = P_{i,j}$) units. Find the minimum amount of money FJ needs so that every field is either connected to a field that has water or has its own well.

The first line contains an integer $n$. The next $n$ lines each contain an integer $W_i$. The next $n$ lines each contain $n$ integers; the $j$-th number in the $i$-th line is the cost $P_{i,j}$ to connect field $i$ and field $j$.

Output the minimum cost.

Constraints: For $100\%$ of the testdata, $1 \leq n \leq 300$, $1 \leq W_i \leq 10^5$, $0 \leq P_{i,j} \leq 10^5$. Translated by ChatGPT 5