编程思维训练趣味任务(十二)

一个社区由9个城镇由一个广泛的道路系统连接起来。要求拓宽一些现有的道路。一项调查显示了拓宽每一段道路的成本，结果如下图所示。费用以当地货币表示。委员会不关心卡车是否走最短的路线。它只要求有一种方式，卡车将能够从任何一个城镇行驶到社区中的任何其他城镇。委员会必须支付的最小的总费用是多少？

image.png

策略思路：
1、每个节点与相邻节点之间中最短的线
2、每三个相邻节点之间避开最长的边；
3、选择易于算法编码实现的表达方式；

图1-4 表达策略的实现过程

image.png image.png image.png image.png

算法实现易于字典结构表达：

image.png

# 字典表达图的节点连接

graph = {'A': set(['B', 'C', 'D']),
         'B': set(['A', 'C', 'J']),
         'C': set(['A','B', 'D', 'E','F']),
         'D': set(['A', 'C', 'F']),
         'E': set(['C', 'G', 'H']),
         'F': set(['D', 'G']),
         'G': set(['E', 'F', 'H']),
         'H': set(['E', 'G', 'J']),
         'J': set(['B', 'H'])}

print(graph['A'])

再继续算法实现之前，请参考历史文章，关于最短路径的一种效率比较低的写法。

疫情后想游遍中国几个大城市，每个城市之间坐高铁。为了节省成本需要规划线路，约束条件是：
每个城市只去一次；
整个旅程的总费用最少；