简答题 偏难
#17223

试题名称 :货物运输 时间限制 :1.0 s 内存限制 :512.0 MB

试题名称:货物运输

时间限制:1.0 s

内存限制:512.0 MB

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:python;toolbar:false;"># 递归深度扩容,防止长树DFS栈溢出 import sys sys.setrecursionlimit(int(1.5e5)) n = int(input())  # 树的节点总数 # 邻接表 e[u] 存储 [相连节点, 边权长度] e = [[] for _ in range(n + 1)] total_edge_sum = 0  # 所有边的总长度 # 建树,无向树 for _ in range(n - 1):     u, v, w = map(int, input().split())     e[u].append([v, w])     e[v].append([u, w])     total_edge_sum += w # DFS:返回起点1到以u为根的子树内最远点距离 # u: 当前节点 fa: 父节点 d: 首都(1)到u的距离 def dfs(u, fa, d):     max_dist = d  # 初始最远距离为当前节点自身距离d     for neighbor, weight in e[u]:         if neighbor != fa:             # 递归子节点,更新全局最远距离             sub_max = dfs(neighbor, u, d + weight)             max_dist = max(max_dist, sub_max)     return max_dist # 公式推导:遍历整棵树每条边会走2次,减去最长一条单程路径(不用折返) longest_path = dfs(1, 0, 0) ans = total_edge_sum * 2 - longest_path print(ans)</pre>
这道题暂未补解析。