森林国有15个城市,国王想在城市间修建铁路。因为地形和气候原因,修建每条铁路的花费有高有低。
设计师向国王提供了规划图,图中每棵树代表一个城市,城市间有灰线连接,表示两个城市间可以修建铁路,费用在旁边标出。如下图所示:
国王希望新修建的铁路能使任何两个城市互通,又不想花太高的代价。如果只选择部分路段修建铁路,最小总花费是( )。
24
30
31
25