大臣的旅费-动规/深搜

简介: 大臣的旅费-动规/深搜

题目描述


很久以前,T 王国空前繁荣。为了更好地管理国家,王国修建了大量的快速路,用于连接首都和王国内的各大城市。

为节省经费,T 国的大臣们经过思考,制定了一套优秀的修建方案,使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时,如果不重复经过大城市,从首都到达每个大城市的方案都是唯一的。

J 是 T 国重要大臣,他巡查于各大城市之间,体察民情。所以,从一个城市马不停蹄地到另一个城市成了 J 最常做的事情。他有一个钱袋,用于存放往来城市间的路费。

聪明的 J 发现,如果不在某个城市停下来修整,在连续行进过程中,他所花的路费与他已走过的距离有关,在走第 x 千米到第 x +1 千米这一千米中( xx 是整数),他花费的路费是 x +10 这么多。也就是说走 1 千米花费 1,走 2 千米要花费 23。

J 大臣想知道:他从某一个城市出发,中间不休息,到达另一个城市,所有可能花费的路费中最多是多少呢?


输入描述


输入的第一行包含一个整数 n,表示包括首都在内的 T 王国的城市数。

城市从 1 开始依次编号,1 号城市为首都。

接下来 nn -1 行,描述 T 国的高速路( T 国的高速路一定是 nn -1 条)。

每行三个整数 Pi,Qi,Di,表示城市 Pi 和城市 Qi 之间有一条高速路,长度为 Di 千米。


输出描述:


输出一个整数,表示大臣 J 最多花费的路费是多少。


输入输出样例


示例

输入

1. 5
2. 1 2 2
3. 1 3 1
4. 2 4 5
5. 2 5 4

输出

135

样例说明

大臣 J 从城市 4 到城市 5 要花费 135 的路费。


运行限制


  • 最大运行时间:5s
  • 最大运行内存: 64M


思路


状态定义:定义dp[u]表示以u为根节点的子树上,从u出发能到达的最远路劲长度。

状态转移方程:我们设u有t个邻居子节点,v1,v2,⋯,vt,那么 dp[u] 的值可以这样计算:


dp[u]=max(dp[vi]+edge(u,vi))

其中,1 ≤ i ≤ t

我们可以通过一次深度优先搜索,到达树的叶子节点,从下往上逐层更新,得出最长距离


代码


1. def dfs(u):
2. global maxlen
3.     vis[u]=1
4. for v,edge in e[u]:
5. if vis[v]==1:
6. continue
7.         dfs(v)
8.         maxlen=max(maxlen,dp[u]+dp[v]+edge)
9.         dp[u]=max(dp[u],dp[v]+edge)
10. 
11. 
12. n=int(input())
13. e=[list() for i in range(n+1)]
14. for i in range(n-1):
15.     a,b,c=map(int,input().split())
16.     e[a].append((b,c))
17.     e[b].append((a,c))
18. 
19. vis=[0 for i in range(n+1)]
20. dp=[0 for i in range(n+1)]
21. maxlen=0
22. dfs(1)
23. 
24. print(maxlen*10+max len*(maxlen+1)//2)
目录
打赏
0
0
0
0
8
分享
相关文章
F : 吃奶酪(深搜)
这篇文章提供了一个使用深度优先搜索(DFS)解决的算法问题,即“吃奶酪”问题,其中包含C++代码实现,目标是计算一只小老鼠吃掉所有奶酪的最少距离,通过预处理奶酪间的距离和使用剪枝技术来优化搜索过程。
讲课:拓扑排序、最短路算法
讲课:拓扑排序、最短路算法
转变命运!揭秘反转链表的神奇算法!
转变命运!揭秘反转链表的神奇算法!
关押罪犯(并查集加点问题最详细讲解)
关押罪犯(并查集加点问题最详细讲解)
99 0
关押罪犯(并查集加点问题最详细讲解)
回溯算法——我欲修仙(功法篇)
回溯算法——我欲修仙(功法篇)
114 0
二分查找——我欲修仙(功法篇)
二分查找——我欲修仙(功法篇)
101 0
KMP算法——我欲修仙(功法篇)
KMP算法——我欲修仙(功法篇)
122 0
【牛客】二叉树遍历
【牛客】二叉树遍历
62 0

热门文章

最新文章