Okay, so I tried to do some stuff.
I made a tree in java, and did some simple hueristic MST-type stuff.
I've only done the US Map so far...but I might code up some more maps later. I can't see the attachments AdamH put up, so I didn't bother to make a text parser...if I can get them visible, I could try to build a parser for it.
Anyways, the interesting bits are the results:
So, US Map including/excluding various regions. I did a simple heuristic MST for it (just take the cheapest connection from the current MST and add that city). I'm pretty sure this works for us because we're directionless, but I don't feel like proving it.
Here's the total costs for those trees for each possible 4-region set:
Green, Brown, Blue, Purple: ILLEGAL
Purple, Blue, Red, Brown: ILLEGAL
Green, Brown, Yellow, Blue: ILLEGAL
Green, Brown, Yellow, Red: 134
Green, Brown, Red, Purple: 147
Green, Brown, Yellow, Purple: 154
Green, Red, Yellow, Purple: 159
Brown, Red, Yellow, Purple: 163
Green, Brown, Red, Blue: 181
Green, Red, Blue, Purple: 191
Green, Red, Yellow, Blue: 193
Brown, Red, Yellow, Blue: 197
Brown, Yellow, Purple, Blue: 200
Green, Yellow, Purple, Blue: 201
Yellow, Red, Blue, Purple: 208
So, then I allowed you to visit each node 3 times, and built 68 cities. There are several problems with this as an approximation of total costs but based on the later stuff it's not too bad.
Just cheapest and most expensive this time:
Green, Brown, Red, Yellow: 529
Red, Yellow, Blue, Purple: 663 (starting from phoenix)
Note: here starting city matters, and it's clearly not optimal. I think the issue is probably that it builds some double-connections before single connections that open up cheaper regions. In particular it's cheaper to build the SouthWest out before you triple-up in the fargo area. Even though that first connection is more expensive.
Then I just had it do 4 of these simultaneously. This goes 1-city at a time and builds out to 17 cities per "player"
This is maybe the most interesting for analyzing starting positions although it's a far cry from a simulation. Interestingly the total is cheaper than above...I'm supposing it's due to the 4 "free" connections for starting cities.
Green, Brown, Red, Yellow: 125, 130, 139, 128: 522
(Savannah, NewYork, OklahomaCity, Duluth)
Red, Yellow, Blue, Purple: 208, 144, 152, 154: 658
(LA, Fargo, Houston, Cheyenne)
For the cheap map, it's pretty stable regardless of where you start (though if you clump everyone together cost goes up a bit). For the expensive map it is highly unstable. It's really interesting to see how starting positions effect one another. Especially the LA-player. His starting position is obviously terrible using this method, but if you move him elsewhere he's too close to another player and only goes down to ~ 190 while driving them up to similar values.
Anyways, enjoy.