← 返回题目列表

AtCoder · abc073_d

D. joisino的旅行

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

有 N Atcoder 州的城镇,由以下连接 M 双向道路。

的 i第条路连接城镇 A_i 和 B_i 的长度为 C_i.

乔伊西诺来访 R 该州的城镇, r_1,r_2,..,r_R (不一定按此顺序)。

她将飞往她访问的第一个城镇,并从她访问的最后一个城镇飞回,但在剩余的行程中,她将不得不通过公路旅行。

如果她按照公路行驶距离最短的顺序访问城镇,那么该距离是多少?

约束

  • 2≤N≤200
  • 1≤M≤N×(N-1)/2
  • 2≤R≤min(8,N) (min(8,N) 是以下较小者 8 和 N.)
  • r_i≠r_j (i≠j)
  • 1≤A_i,B_i≤N, A_i≠B_i
  • (A_i,B_i)≠(A_j,B_j),(A_i,B_i)≠(B_j,A_j) (i≠j)
  • 1≤C_i≤100000
  • 每个城镇都可以通过公路到达每个城镇。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M R
r_1 ... r_R
A_1 B_1 C_1
:
A_M B_M C_M

输出

如果 Joisino 按最小顺序访问城镇,则打印公路行驶的距离。


示例输入 1

3 3 3
1 2 3
1 2 1
2 3 1
3 1 4

示例输出 1

2

例如,如果她按照以下顺序访问城镇 1, 2, 3,行驶的距离将为 2,这是可能的最小值。


示例输入 2

3 3 2
1 3
2 3 2
1 3 6
1 2 2

示例输出 2

4

城镇之间的最短距离 1 和 3 is 4。因此,无论她是否访问城镇 1 or 3 首先,行驶的距离将为 4.


示例输入 3

4 6 3
2 3 4
1 2 4
2 3 3
4 3 1
1 4 1
4 2 2
3 1 6

示例输出 3

3