#P955. 树上游走(二)

树上游走(二)

题目描述

给定一个棵由编号为 11~nnnn 个节点构成的树,及 mm 个关键节点,树的第 ii 条双向边连接 ui,viu_i,v_i ,长度为 wiw_i。你可以从树上任何一个节点出发开始游走,到任何一个节点结束,但整个游走过程中必须经过给定的 mm 个关键节点。

请问,应当如何设计路线,能够使得整个游走过程中,经过的路径长度最短。

输入格式

输入第一行,两个正整数 n,mn,m 接下来 n1n-1 行,每行 33 个正整数,其中第 i+1i+1 行分别表示第 ii 条边的ui,vi,wiu_i,v_i,w_i。 输入最后行,mm 个正整数,分别表示 mm 个关键节点的编号cic_i

输出格式

输出共一行,表示所求最短长度。

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

数据范围

  • 对于 30%30\% 的数据,1mn1001\leq m \leq n \leq 100
  • 对于 60%60\% 的数据,1mn1041\leq m \leq n \leq 10^4
  • 对于 100%100\% 的数据,1mn1051\leq m \leq n \leq 10^51ui,vi,cin1 \leq u_i,v_i,c_i \leq n1wi1041 \leq w_i \leq 10^4