下图标明了六个城市(A～F)之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路，使各个城市之间均可通过高速公路通达，至少要改造总计(66)公里的公路，这种总公里数最少的改造方案共有(67)个。