最长路径

[编程题]最长路径

热度指数：1809 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

城市 $A$ 新建了 $n$ 个座房子，城市规划处用 $n-1$ 条双向街道将房子连在一起，使得任意两座房子之间有且仅有一条道路可达。牛牛和牛妹将被随机分到两个房子，现在牛牛想知道，他和牛妹房子的最长路径是多少。

示例1

输入

7,[2,3,5,4,5,5],[5,2,1,6,7,4],[15,6,14,4,1,6]

输出

说明

当牛牛和牛妹分别被分到  ,  两个房子时，路径最长。

备注:

房子  , 房子  , 街道长度 。
表示房子  与房子  之间有一条长度为 的道路相连。
 。

算法知识视频讲解

Python 3

ZhongHaoWang

等价于找树的直径

import collections
class Solution:
    def solve(self, n, u, v, w):
        # write code here
        edges = collections.defaultdict(list)
        dis = {}
        k = len(u)
        for i in range(k):
            edges[u[i] - 1].append(v[i] - 1)
            edges[v[i] - 1].append(u[i] - 1)
            dis[(v[i] - 1, u[i] - 1)] = w[i]
            dis[(u[i] - 1, v[i] - 1)] = w[i]

        node, d = -1, 0

        def dfs(cur_node, cur_dis, visited):
            nonlocal node, d, edges
            if cur_dis > d:
                node = cur_node
                d = cur_dis
            for next_ in edges[cur_node]:
                if next_ not in visited:
                    visited.append(next_)
                    dfs(next_, cur_dis + dis[(cur_node, next_)], visited)
            return

        dfs(0,0,[0])
        dfs(node,0,[node])
        return d

发表于 2021-08-29 18:42:00 回复(0)