Problem 2

Four towns are situated such that the distances in miles (as the crow flies) between each town are given by the following table:

	Alphaville	Bravotown	Charliepool	Deltaford
Alphaville	0	284	355	213
Bravotown		0	213	355
Charliepool			0	284
Deltaford				0

The government wants to construct an entirely new motorway network so that all four towns are connected, but the total cost is minimised. If new motorway costs £30 million per mile, what is the minimum cost required to build the new network? You may assume that the country between all the towns is perfectly flat.

Please enter your answer to the nearest million pounds, i.e. if you think the answer is 56.12 million, then just enter 56. If you think the answer is exactly 42.5 million, then you should round up and enter 43.