#P955. 树上游走(二)
树上游走(二)
题目描述
给定一个棵由编号为 ~ 这 个节点构成的树,及 个关键节点,树的第 条双向边连接 ,长度为 。你可以从树上任何一个节点出发开始游走,到任何一个节点结束,但整个游走过程中必须经过给定的 个关键节点。
请问,应当如何设计路线,能够使得整个游走过程中,经过的路径长度最短。
输入格式
输入第一行,两个正整数 接下来 行,每行 个正整数,其中第 行分别表示第 条边的。 输入最后行, 个正整数,分别表示 个关键节点的编号
输出格式
输出共一行,表示所求最短长度。
5 3
1 2 2
2 3 4
2 4 5
1 5 1
3 4 5
15
样例解释 1
3-->2-->1-->5-->1-->2-->4 4 2 1 1 2 5
数据范围
- 对于 的数据,
- 对于 的数据,
- 对于 的数据,,,