题目描述

blablabla

样例

bfs写法，较为简单，与前面不太一样的是，这里队列只存了节点，然后从节点里面去获取它的邻居，也就是一开始输入时候的，那个向量邻接表，每次遍历一次地方，判断一个从起点到过这个地方没有，只有没有，才会添加这个新节点。去计算这个距离和替换最远节点，一层层的从队列左端提取，直到遍历完所有的点。

另外附上一份dfs的代码，额，dfs只能过11/12个，而且理解上没有bfs那么直接，而且大部分能用dfs的都能用bfs解决，我是打算专精bfs，dfs真遇到能够理解就行。
现在说说两个实现上的不同，由于bfs是全局上去遍历，因此能够维护一个距离数组dis=[-1]*n,因此，我们能够去记录从起点开始到后面的距离，能够判断是否为-1来确保我们不会走回头路。而dfs是用递归，不能够维护这么个全局的东西，要用到一个父亲节点的参数来辅助，确保邻居不会回到父节点，然后距离是通过比较大小，然后return，不断return来得到的。逻辑上不那么直观。

from collections import deque
def bfs(graph,start,n):
    dis=[-1]*(n+1)
    dis[start]=0

    queue=deque([start])
    fathest,max_dis=start,0

    while queue:
        node=queue.popleft()
        for neighbor,length in graph[node]:
            if dis[neighbor]==-1:
                dis[neighbor]=dis[node]+length
                queue.append(neighbor)
                if dis[neighbor]>max_dis:
                    max_dis,fathest=dis[neighbor],neighbor

    return fathest,max_dis



n=int(input())
graph=[[] for _ in range(n+1)]
for i in range(n-1):
    p,q,d=map(int,input().split())
    graph[p].append((q,d))
    graph[q].append((p,d))

fathest,dis1=bfs(graph,1,n)
_,dis2=bfs(graph,fathest,n)
cost=10*dis2+(1+dis2)*dis2//2
print(cost)

dfs代码

def dfs(node,parent,graph,dist):
    fathest,max_dis=node,dist

    for neighbor,length in graph[node]:
        if neighbor!=parent:
            new_fathest,new_dist=dfs(neighbor,node,graph,dist+length)
            if new_dist>max_dis:
                fathest,max_dis=new_fathest,new_dist

    return fathest,max_dis



n=int(input())
graph=[[] for _ in range(n+1)]
for i in range(n-1):
    p,q,d=map(int,input().split())
    graph[p].append((q,d))
    graph[q].append((p,d))

fathest,dis1=dfs(1,-1,graph,0)
_,dis2=dfs(fathest,-1,graph,0)
cost=10*dis2+(1+dis2)*dis2//2
print(cost)

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla