← 返回题目列表

AtCoder · codequeen2025_final_g

G. 全国巡演

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

配点 : 525 点

問題文

在日本 N 有多个城市,并且城市双向相连。 M 有一条真正的路。城中之城 1 来自城市 它的编号最大为 N 。 i 真正的道路是城市 U_i 和城市 连接 V_i ,长度 C_i 这是一条公里长的路。除了公路之外,城市之间的旅行是不可能的。

另外, N 的城市 K 有一个现场表演场地。具体来说, k=1,2,\ldots,K 对抗城市 现场演出场地位于 A_k 。在这里,K 是 它仅由 4 凌驾于城市之上 1 和城市 连接 N 保证有现场演出场地。

人气偶像团体Bit♡Beat决定举办全国巡演。

全国巡演有所不同。 4 它将在三个城市的现场场地举行。另外,第一次live将在城市举行 1 ,最后一次直播是在城里 必须使用 N 来完成。 从

都市 1 开始 4 一城 1,N 在城市现场表演,包括 求到达 N 所需的最短距离。

但是,您在旅途中可能会多次访问同一城市。

制約

  • 4\le N\le 10^5
  • \displaystyle N-1 \le M\le \min\left(2\times 10^5, \frac{N(N-1)}2 \right)
  • 1\le U_i < V_i \le N
  • 1\le C_i \le 10^9
  • 给定的图很简单且连通
  • 4\le K\le N
  • 1 = A_1 < A_2 < \ldots < A_K = N
  • 所有输入值均为整数

入力

输入将以以下形式从标准输入给出。

N M K
A_1 A_2 \ldots A_K
U_1 V_1 C_1
U_2 V_2 C_2
\vdots
U_M V_M C_M

出力

以公里为单位打印出您的答案。但是,不输出单位,而是将答案输出为整数。


入力例 1

5 4 4
1 2 4 5
1 3 1
2 3 10
3 4 100
4 5 1000

出力例 1

1121

通过如下移动 4 您可以在三个城市现场表演: 住在

  • 都市 1 。
  • 都市 1 来自城市 它的编号最大为 3 至 1 移动公里数。
  • 都市 3 来自城市 它的编号最大为 2 至 10 移动公里数。
  • 都市 2 。
  • 都市 2 来自城市 它的编号最大为 3 至 10 移动公里数。
  • 都市 3 来自城市 它的编号最大为 4 至 100 移动公里数。
  • 都市 4 。
  • 都市 4 来自城市 它的编号最大为 5 至 1000 移动公里数。
  • 都市 5 。

在这种情况下行驶的距离是 1121 公里。

行驶距离为 1121 由于不可能移动不到一公里, 请输出 1121 。


入力例 2

6 11 4
1 4 5 6
1 2 40
2 3 30
3 6 20
1 4 100
2 4 80
3 4 60
4 6 40
1 5 80
2 5 70
3 5 60
5 6 50

出力例 2

210

入力例 3

15 22 5
1 5 11 13 15
1 2 668
1 6 869
2 3 633
2 7 563
3 4 32
3 8 158
4 5 314
4 9 859
5 10 935
6 7 826
6 11 167
7 8 112
7 12 606
8 9 279
8 13 731
9 10 181
9 14 442
10 15 557
11 12 499
12 13 174
13 14 791
14 15 477

出力例 3

2977