简答题
偏难
#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>
这道题暂未补解析。