题目背景
在《西游记》的世界中,孙悟空、猪八戒、沙僧和唐僧一起踏上了取经之路。他们面临着各种妖魔鬼怪的阻挠,需要找到一条最优的路线来避开危险。
题目描述
取经路上,孙悟空、猪八戒、沙僧和唐僧遇到了N个城市,其中K个城市被妖魔鬼怪占领。城市之间有N-1条路连接,每条路有一个破坏的代价。现在,你作为有智慧的和尚,需要计算最小的代价,使得这K个妖魔鬼怪被隔离开,以便后续逐个击败它们。
输入格式:
第一行包含两个正整数N和K,分别表示城市的数量和被占领的城市数量。
第二行包含K个整数,表示被占领的城市编号。
接下来N-1行,每行包含三个正整数A、B和C,表示从A城市到B城市有一条路,破坏这条路的代价为C。
城市编号从0开始。
输出格式:
输出一行一个整数,表示最小的代价。
输入样例#1:
5 3
1 2 4
1 0 4
1 3 8
2 1 1
2 4 3
输出样例#1:
4
说明:
为了隔离掉城市1、2和4,我们可以选择破坏从城市1到城市2的路和从城市2到城市4的路,总代价为4。
2<=K<=N<=10^4,1<=C<=10^9。