3739: 躲避技能(第二轮01)
题目描述
鸡尾酒是一个多操手，他可以同时操作 m 个账号。今天， 他使用这些账号一起 打一个 boss。这个 boss 战的地图共有 n 个关键点， 其中有 n − 1 条边， 每 条边连接着两个不同的点，使得从任意点出发可以到达其他所有的点。鸡尾酒的 m 个账号分别编号 1 至 m ， 一开始，第 i 个账号在点 si 。可能有两个账号 在同一位置。
现在，boss 放出了一个致命技能。boss 在地图上标出了 m 个关键点，想成功 躲避这个技能，必须在每一个被标记的点上，都有一个账号站在上面。注意， 可 能会有点被多次标记，多次标记的点需要有多个账号站在上面。
由于鸡尾酒无法分身，所以他必须先把一个账号移动到一个位置，才能动另一个 账号， 不能同时移动多个账号。假设鸡尾酒的任意账号通过第 i 条边的时间为 wi，请帮鸡尾酒求出他成功躲避技能所需要的最少时间。
输入
一行两个正整数 n 和 m ，分别表示关键点的数量和标记点的数量。 后面一行 m 个数字 s1, s2 , … , sm , si 表示第 i 个账号的初始位置。 再后面一行 m 个数字，表示标记点的位置。
后面 n − 1 行每行三个数字 ui, vi, wi，表示有一条连接 ui, vi 的边，经过时间 为 wi 。
由于boss想要为难鸡尾酒，所以所有的 wi 都是反着给出的，即低位在前，高位在后，没有前导零(输入的最后一位)。
输出
一行一个正整数，表示最少时间。
样例输入 复制
6 4
5 1 3 2
4 2 1 2
1 2 5
2 3 6
2 4 7
1 5 4
1 6 4样例输出 复制
22提示
【样例 1 输入】
6 4
5 1 3 2
4 2 1 2
1 2 5
2 3 6
2 4 7
1 5 4
1 6 4
【样例 1 输出】
22
【样例 2 输入】
10 3
2 3 4
1 8 10
1 2 5
1 3 6
1 4 7
3 5 11
4 6 11
5 9 43
6 7 34
9 10 13
7 8 42
【样例 2 输出】
159
【样例 3 输入】
2 10
1 1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2 2
1 2 1234567891001987654321
【样例 3 输出】
12345678910019876543210
【数据范围】
请使用较快的输入方式。
本题共 25 个数据点，每个测试点等分(即一个测试点 4 分)。 保证对于所有数据， 1 ≤ n, m ≤ 10^5, 1 ≤ wi ≤ 10^100 。
保证对于 20% 的数据， 1 ≤ n, m ≤ 10,1 ≤ wi ≤ 10^5 。 保证对于另外 20% 的数据， 1 ≤ m ≤ 10,1 ≤ wi ≤ 10^5 。 保证对于另外 40% 的数据， 1 ≤ wi ≤ 10^5 。