徐老师的城市重建
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
徐老师最近在玩的星战游戏非常有趣！
甚至可以自己建造星际城市，但是这个游戏存在战争系统，你可以进攻他人的城市，占领他们的城市来获得资源
有一天睡醒以后，徐老师打开游戏发现自己的城市被全部摧毁了！
这可是徐老师花费了不知道多少天的心血好不容易打造的城市，整理心情后的徐老师决定先检查一下城市的状况
城市中共有 $n$ 个资源收集点，然而一个资源点的资源并不足以让徐老师快速重建城市
经过徐老师的仔细观察，他发现还剩下 $m$ 条运输路线可以快速修复，其中第 $i$ 条运输路线连通 $u,v$ 两个编号的资源收集点，修复需要花费 $w$ 个金币
然而修复那么多运输路线实在是太耗费金币了，徐老师并不想在游戏里氪金
经过他再次更加仔细的观察，他整理出了 $k$ 个资源收集点的编号，这 $k$ 个点的资源远多于其他的资源收集点
所以他只要在这 $k$ 个点中选出两个资源收集点，并将它们之间的运输路线打通，即可获得足够的资源重建城市
现在徐老师想知道，他最少需要花费多少金币来修复运输路线？
P.S. 题目并不保证任意两点之间存在运输路线，可能两个资源收集点之间的连通需要经过其他资源收集点
输入格式
第一行包含一个整数 $T\ (1\le T\le 10)$，代表测试用例的数量。
对于每组测试用例，第一行包含两个整数 $n,m\ (1\le n,m\le 100000)$，代表资源收集点的数量和运输路线的数量
接下来 $m$ 行每行包含三个整数 $u_i,v_i,w_i\ (1\le u_i,v_i\le n,1\le w_i\le 100000)$。表示一条运输路线连接 $u_i$ 和 $v_i$，修复需要花费 $w_i$ 的金币
然后一行包含一个整数 $k\ (1\le k\le n)$，表示徐老师选出来的 $k$ 个资源收集点编号
然后一行包含 $k$ 个互不相同的整数 $a_i\ (1\le a_i\le n)$，代表每个资源收集点的编号
| 数据组号 | n | m | k |
| :---: | :---: | :---: | :---: |
| 1 | 10 | 10 | 10 |
| 2 | 500 | 100000 | 2 |
| 3 | 100000 | 100000 | 2 |
| 4~5 | 100000 | 100000 | 20 |
| 6~10 | 100000 | 100000 | 100000 |
题目保证输入的图一定连通
输出格式
共 $T$ 行，每行一个整数表示徐老师最少需要花费的金币数量
样例
1
5 6
1 2 1
2 3 3
3 1 3
2 5 1
2 4 2
4 3 1
3
1 3 522023暑CSP-S复赛集训模拟赛一
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 3
- 开始于
- 2023-7-28 22:00
- 结束于
- 2023-8-7 22:00
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 21
