#abc277e. [abc277_e]Crystal Switches

[abc277_e]Crystal Switches

【题面翻译】

给定一张 nn 个点 mm 条边的无向图。每条边有一个权值 w{0,1}w \in \{0, 1\}w=0w = 0 表示这条边无法通过,w=1w = 1 则可以通过。

kk 个点上面有按钮 sis_i

你现在位于 11 号点。每次,你可以做两件事情中的一件:

  1. 移动。移到相邻的一个点上,注意这条边一定是可以通行的。
  2. 按开关。此时,全部路的边权取反。即:w=0w = 0 变成 11w=1w = 1 变成 00

请问你是否能够到达 nn 号点。如果可以,求出最少移动次数。

translated by

https://www.luogu.com.cn/user/367488

【输入格式】

第一行三个数 n,m,kn, m, k

接下来 mm 行,每行三个数 ui,vi,wiu_i, v_i, w_i表示一条连接 uiu_iviv_i 的边。

最后一行 kk 个数,表示按钮的位置。

【输出格式】

如果无法到达,输出 1-1。否则输出最少移动次数。

【数据范围】

2n2×1052 \le n \le 2 \times 10^5

1m2×1051 \le m \le 2 \times 10^5

1kn1 \le k \le n

保证 1ui,vin1 \le u_i, v_i \le n,且 uiviu_i \ne v_i

保证 1s1<s2<<skn1 \le s_1 < s_2 < \cdots < s_k \le n