2538: 逐个击破
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：0
题目描述
三大战役的平津战场上,傅作义集团在以北平、天津为中心,东起唐山西至张家口
的铁路线上摆起子一字长蛇阵,并企图在溃败时从海上南逃或向西逃窜。为了就地歼敌
不让其逃走,毛泽东制定了先切断敌人东洒两头退路然后再逐个歼灭敌人的战略方针。
秉承伟大军事家的战略思想,作为一个有智慧的军长你,遇到了一个类似的战场局面:
现在有 N 个城市,其中 K 个被敌方军团占领了,N 个城市间有 N-1 条公路相连,破
坏其中某条公路的代价是已知的,现在,告诉你 K 个敌方军团所在的城市,以及所有公
路破坏的代价,请你算出花费最少的代价将这 K 个地方军团互相隔离开,以便第二步逐
个击破敌人。
输入
第一行包含两个正整数 n 和 k。
第二行包含 k 个整数,表示哪个城市别敌军占领。
接下来 n-1 行,每行包含三个正整数 a,b,c,表示从 a 城市到 b 城市有一条公路,
以及破坏的代价 c。城市的编号从 0 开始计数。
输出
一行一个整数,表示最少花费的代价。
样例输入 复制
3 3
0 1 2
0 1 1
1 2 2样例输出 复制
3提示
attack.in
5 3
1 2 4
1 0 4
1 3 8
2 1 1
2 4 3
attack.out
4
10%的数据满足 2<=n<=10;
100%的数据满足 2<=n<=100000;2<=k<=n;1<=c<=1000000。