Some algorithms are more difficult than others.  The brute force (obvious) method might work, but it also might take more time than you’re willing to spend, both in development and in the actual running of it.

I finally figured out the fast method and the data was indeed well worth the effort. As an alternate victory condition, I was toying with the idea of connecting some N subset of 27 special cities, the “any” cities.  The “any” cities are the cities that wind up on the “Any” cards in the city distribution deck; they are the cities with the highest probabilities in each of the nine regions.

I needed to see what the cheapest single network would be to see how it would compare to the net worth victory condition.  It turns out that the cheapest single network that could connect all 27 cities only costs $151,000. For 24, it’s $119,000; for 21, it’s $102,000. This tells me that limiting the alternate victory condition to 21 or 24 is a mistake. The full 27 should work.