农夫约翰要搬家了!
他正在寻找建立新农场的最佳地点,以最大程度地减少他每天需要走的行程。
约翰计划迁往的地区有 N 个城镇,编号 1∼N,共有 M 条双向道路连接某些对城镇。
所有城镇之间都是互通的。
约翰需要你的帮助来选择最佳城镇作为他的新农场的坐落点。
约翰每天都要去 K 个有市场的城镇采购。
具体地说,他每天从新农场所在的城镇出发,访问这 K 个有市场的城镇,然后返回新农场。
约翰可以按照他希望的任何顺序访问这些有市场的城镇。
在选择要建立新农场的城镇时,约翰希望仅从没有市场的 N−K 个城镇中进行选择,因为这些城镇的房屋价格较低。
如果约翰将农场建在最佳位置,并尽可能巧妙地安排前往市场的行程,请帮助约翰计算他每日所需的最小行程。
第一行包含三个整数 N,M,K。
接下来 K 行,每行包含一个 1∼N 范围内的整数,表示一个有市场的城镇的编号。
接下来 M 行,每行包含三个整数 i,j,L,表示城镇 i 和 j 之间存在一条长度为 L 的双向道路。
输出约翰每日所需的最小行程长度。
5 6 3
1
2
3
1 2 1
1 5 2
3 2 3
3 4 5
4 2 7
4 5 10
12
最佳方案为在城镇 5 建立农场,每日路线为 5−1−2−3−2−1−5,总长度为 12。
数据范围
1≤N≤10000,
1≤M≤50000,
1≤K≤5,
1≤i,j≤N,
1≤L≤1000