目录
python最短路径和
第十五届蓝桥杯青少年组python比赛选拔赛真题
一、题目要求
（注：input（）输入函数的括号中不允许添加任何信息）
1、编程实现
蚂蚁王国住着 N 只蚂蚁，每只蚂蚁都有自己的领地，领地之间可以直接到达或经过其他领地间接到达，可以直接到达的领地之间的道路距离都为1，但所有领地都有一条唯一的最短路径可以相互到达。
现要在 N 块领地(依次编号为 1~N)中，选出一块领地建立游乐场，使得所有蚂蚁到游乐场的最小距离总和是 N 种情况中最小的,例如:N=8,1~8号领地之间的连接关系为:1和5、2和6、3和 6、4和 5、5和 6、4和 7、5 和 8。
如果将游乐场创建在5 号领地，最小距离总和为 10。
- 1 号到5号距离为 1;
- 2 号到5 号距离为 2;
- 3 号到5 号距离为 2;
- 4 号到5 号距离为1;
- 6 号到5 号距离为1;
- 7 号到 5 号距离为 2:
- 8 号到5号距离为1。
如果将游乐场创建在 6号领地，最小距离总和为 12。
- 1号到6号距离为2;
- 2号到6号距离为1;
- 3号到6号距离为1;
- 4号到6号距离为2
- ;5 号到6号距离为1;
- 7 号到 6 号距离为 3;
- 8 号到6号距离为 2。
可以发现，将游乐场创建在5 号领地，最小距离总和 10 是最小的，故输出 10。
2、输入输出
输入描述：第一行输入一个正整数 N(2≤N≤20)，表示领地数量
接下来输入 N1行，每行包含两个正整数(1≤正整数≤N,两个正整数不相同),表示两块领地相互之间可以直接到达，正整数之间以一个英文逗号隔开(数据保证 N 块领地相互之间可以到达)
输出描述：只有一行，一个整数，即N 种情况中最小距离总和的最小值
输入样例：
8
1,5
2,6
3,6
4,5
5,6
4,7
5,8输出样例：
10二、算法分析
- 题目相对而言还是有一定难度的，这是比较典型的无向图最小代价问题
- 解决这类题目，如果小朋友们没有学过一点点算法的思路，解这道题会复杂点
- 小兔子老师这里使用深度优先算法进行求解
- 使用递归函数进行深度优先搜索，找到从每个节点出发到其他所有节点的代价，然后选取最小值作为结果，需要逐个节点进行遍历
- 具体实现如下：
三、程序编写
n = int(input())
ls = []
for x in range(n-1):
path = list(map(int,input().split(',')))
ls.append(path)
def findNext(p):
lst = []
for i in range(n-1):
if p in ls[i]:
np = sum(ls[i])-p
if visited[np]==False:
lst.append(np)
return lst
def cost(p,cnt):
nodes = findNext(p)
if len(nodes)==0:
return 0
visited[p] = True
res = 0
for node in nodes:
res = res + cost(node,cnt+1) +cnt
return res
ans=[]
for x in range(1,n+1):
visited = [False]*(n+1)
res = cost(x,1)
ans.append(res)
print(min(ans))四、程序说明
- 首先输入n个节点
- 创建一个空列表用于存储路径信息
- 接着利用for循环结合列表和map依次输入每条路径的信息并添加到列表中
- 定义findNext函数，用于找到与节点p相邻的节点
- 遍历每条路径的信息 ，如果节点p在路径信息中出现，计算出相邻节点的值
- 判断相邻节点是否访问过，没有将相邻节点的值添加到列表中
- 定义cost函数，用于计算从节点p出发的最小代价
- 调用函数findNext获取与节点p相邻的节点
- 如果相邻节点列表为空就返回，表示不需要再继续访问相邻节点
- 访问节点p，并计算出与p相邻节点的值，并返回
- 创建一个空列表用于存储每个节点出发的最小代价
- 遍历每个节点同时创建一个长度为n+1的未访问过的列表
- 接着调用cost函数计算从节点x出发的最小代价
- 将最小代价添加到列表中 ，最后输出最小代价
五、运行结果
8
1,5
2,6
3,6
4,5
5,6
4,7
5,8
10六、考点分析
难度级别：难，这题相对而言还是有点难度，难在算法的设计，具体主要考查如下：
- 学会分析题目，找到解题思路
- 学会递归函数和深度搜索算法的使用和实现
- input函数：Python 中 input() 函数接受一个标准输入数据，返回为 string 类型。
- int函数：强制将传入对象转换成整数类型
- split函数：按照指定的分隔符进行分割
- map函数：将指定的对象按照指定的函数进行迭代，在这里是将时分秒字符串类型数据按int整数类型数字返回输出（相当于多个变量强制类型转化）
- list函数：强制将参数转化成列表对象
- 学会列表的相关操作：列表声明、取数、遍历等等
- 学会for循环的使用：for循环可以遍历任何有序的项及列表元素等等。
- range函数：rang（a,b），循环的时候是不包括b的，所以我们这个案例中要转变一下，要想包含b，就应该写成range(a,b+1)
- 学会if...条件判断语句的使用：满足条件才执行相应的程序
- 学会if...else双分支语句的使用：满足条件执行一种处理程序，不满足执行另一种处理程序
- print函数：用于打印输出，最常见的一个函数。
- 充分掌握for循环、列表和递归函数、深搜算法相关操作函数的使用
PS：方式方法有多种，小朋友们只要能够达到题目要求即可！
七、 推荐资料
1、蓝桥杯比赛
2、考级资料
3、其它资料
- 历届蓝桥杯scratch国赛真题解析
- 历届蓝桥杯scratch省赛真题解析
- 历届蓝桥杯scratch STEMA选拔赛真题解析
- 历届蓝桥杯科技素养计算思维真题解析
- 画图-scratch编程考级99图
- 电子学会历年scratch等级考试一级真题解析
- 电子学会历年scratch等级考试二级真题解析
- 电子学会历年scratch等级考试三级真题解析
- 电子学会历年scratch等级考试四级真题解析
- 零基础学习scratch3.0【入门教学 免费】
- 零基础学习scratch3.0【视频教程 114节 免费】