分数: 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