耐心看完 一定会对你有所帮助 有什么不懂的随时可以私信小郑
深搜虽然很难 但总要面对 如果总是逃避 那就很难进步！
下面呈现的内容将以题目来源+题目分析+代码+知识点学习来源的路线展开
问题来源：1207. 大臣的旅费 - AcWing题库
很久以前，T王国空前繁荣。
为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。
为节省经费，T国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。
同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。
J是T国重要大臣，他巡查于各大城市之间，体察民情。
所以，从一个城市马不停蹄地到另一个城市成了J最常做的事情。
他有一个钱袋，用于存放往来城市间的路费。
聪明的J发现，如果不在某个城市停下来修整，在连续行进过程中，他所花的路费与他已走过的距离有关，在走第x千米到第x+1千米这一千米中（x是整数），他花费的路费是x+10这么多。也就是说走1千米花费11，走2千米要花费23。
J大臣想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？
输入格式
输入的第一行包含一个整数 n，表示包括首都在内的T王国的城市数。
城市从 1 开始依次编号，1 号城市为首都。
接下来 n−1 行，描述T国的高速路（T国的高速路一定是 n−1 条）。
每行三个整数 Pi,Qi,Di,表示城市 PiPi 和城市 QiQi 之间有一条双向高速路，长度为 Di 千米。
输出格式
输出一个整数，表示大臣J最多花费的路费是多少。
题目分析： "如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。"这句话的意思是 连通图不存在环 如果存在环 方案不唯一，所以注意:这里的双向高速路指的是无向图的边，强调无向边的概念，而不是可以重复式来回。如果大臣走了i千米,那么根据题意"在走第x千米到第x+1千米这一千米中（x是整数），他花费的路费是x+10"
总费用=(1+10)+(2+10)+...(i+10)=(1+i)*i/2+10*i 即求i的最大值
那么问题就转化为求任意两个城市间的距离的最大值（距离最大当然大臣走的路程也越大）
那么这就是一个经典问题：求树的直径问题。
树的直径定义：树上任意两节点之间最长的简单路径即为树的「直径」
简单路径：不经过重复点 一次性到达
树的直径有两种常用求法，分别是两次DFS以及树形DP。
本篇只介绍两次DFS 树的直径证明_哔哩哔哩_bilibili
这个证明理解起来不难的，理解了原理再去下手。
Python要实现这种算法 小郑归纳了一下 需要3个容器
一个字典point 用于存储连接关系和连接费用
一个列表res 用于存储某个结点到出发点的费用
一个列表vis 用于表述一个结点是否访问过
n=int(input()) point=dict((i,{})for i in range(n+1)) res=[0 for i in range(n+1)]#初始化 for i in range(n-1): tmp=list(map(int,input().split())) point[tmp[0]][tmp[1]]=tmp[2] point[tmp[1]][tmp[0]]=tmp[2] vis=[0 for i in range(n+1)]#初始化一开始都没有访问过 def dfs(st): for i in point[st]:#遍历st的邻居 to=i#邻居 if not vis[to]:#如果没访问过 vis[to]=1#设置成已访问 res[to]=res[st]+point[st][to]#起点到邻居的距离=起点到st的距离+st到邻居的距离 dfs(to)#深搜下一个结点 vis[1]=1#特殊情况出发点以后防止回到出发点，原因如下 dfs(1)#把1作为起点，假设1连接2，当dfs(2)的时候，不能返回到1 maxlen=max(res)#找到距离出发点最远的点 Q=res.index(maxlen)#端点1 vis=[0 for i in range(n+1)] res=[0 for i in range(n+1)] #恢复 vis[Q]=1 dfs(Q) ans=max(res)#找到距离端点1最远的点 W=res.index(ans)#找到端点2 print(int((1+ans)*ans/2+10*ans))
思路来源于C++这位大佬【朝夕的ACM笔记】树上问题-树的直径 - 知乎 (zhihu.com)
问题来源：“蓝桥杯”练习系统 之算法提高(lanqiao.cn)
zsyzgu是一个弱菜，尽管如此他还是参加了智能体系列赛。智能体系列赛的问题经简化后是这样的，有一只猴子和一些矿点，知道他们在平面上的坐标，这只猴子要经过这些矿点至少一次。假设这只猴子从点A走到点B所要花费的步数是这两个点的曼哈顿距离（即|A.x-B.x|+|A.y-B.y|），问这只猴子经过这些矿点至少一次所需的最少步数。
系列赛中的许多选手都用了贪心的策略，即每次都到最近的没经过的矿点去。但zsyzgu的思路是搜索，这也是他能够摆脱垫底命运获得纪念版T-shirt的原因。
输入格式
第一行两个数表示猴子的坐标；
第二行一个数n表示矿点数；
接下来n行每行两个数表示每个矿点的坐标。
输出格式
一行一个数表示最少步数。
题目分析：给定起始点要求遍历所有所有点花费的最短费用
可采用深搜 类似于迷宫的做法 可以结合我之前有一篇博客 （有模板） 蓝桥杯 迷宫 二叉树 真题小郑的博客-CSDN博客
对于这道题我们先读入数据 将所有点的坐标存到point这样一个二维数组中
建立一个vis数组标记结点是否访问过
定义一个深搜函数 参数由x,y,k构成 x,y代表坐标，k代表到达(x,y)花费的费用
代码难点分析（学习体会）：深搜的重要一点就是回溯
一开始我也觉得挺抽象的，毕竟是递归。下面我解释一下：假设出发点a的应该访问的结点是b,c 存在列表s=[b,c]中 从头开始遍历 那么一开始结点b是没有访问过的 那就尝试把结点b作为下一步，然后继续深搜结点b，对于结点b，遍历所有结点，先访问a，由于a访问过了，那么只能访问c,因为c没有被访问过，然后我们继续深搜c。深搜c的时候，由于a,b都已经被访问过了，那么就可以更新Minstep了，return none。
return none之后做什么呢？想一想，我们深搜c之前做了什么？我们做了：设置结点b已经访问过，为什么要这么设置？因为我们要防止深搜c的时候回到b点！现在，c点已经深搜完毕，；然后结点b需要设置成未访问。原因是这样(这里是难点），请看图
假设有这样一幅图，求a到c的路径方案总数（结点不重复），显然只有两种。
只是现在多了一个结点d，但是不影响。同样的，作为开始点的a，我们需要遍历它所有的邻居，一开始从a出发，然后标记a已访问，然后先深搜b,深搜b的时候，代表从b出发，把b标记为已访问，然后去深搜它的所有邻居。它只有一个邻居，且c是叶子节点，那么直接修改minstep值（对于原题来说相当于），或者说方案数+1，也就是深搜b的邻居这件事做完了。那么此时深搜b这件事情已经做完了一半，因为深搜b的步骤:标记b已经访问，深搜b的邻居，标记b未访问。我们做完了前两项.
还差标记b未访问，也就是我们上面的疑惑点。试想，如果不把b标记为未访问，相当于深搜b的步骤只有刚刚我们做的前两项，那等于我们做完了深搜b这件事，那么现在就要去深搜d
下面开始深搜d，根据步骤，标记d已经访问过，然后去遍历d的邻居，d的邻居a,b，都已经访问过了，那么就不会做任何事情，因为我们dfs某个结点只对他未访问过的邻居操作。所以深搜d这件事，只做了一件事：判断。并没有给出a>>d>>b>>c这条路线，所以不把b标记为未访问这件事首先是不合理的。
下面再看其合理性:试想，如果把b标记为未访问，那么对于d的邻居，只有b未访问，那么我们就去深搜结点b...最终实现方案数+1！大功告成！
x,y=map(int,input().split())#[0,0] n=int(input()) point=[] for i in range(n): point.append(list(map(int,input().split()))) #[[0,1]...] minstep=float('inf') vis=[0 for i in range(n)] def dfs(x,y,k): global minstep,vis,point if k>minstep: return if 0 not in vis: minstep=min(k,minstep) return for i in range(n): if not vis[i]: vis[i]=1 nx=point[i][0] ny=point[i][1] dfs(nx,ny,k+abs(x-point[i][0])+abs(y-point[i][1])) #回溯 vis[i]=0 dfs(x,y,0) print(minstep)
