[ABC277E] Crystal Switches

【题面翻译】 给定一张 $n$ 个点 $m$ 条边的无向图。每条边有一个权值 $w \in \{0, 1\}$。$w = 0$ 表示这条边无法通过，$w = 1$ 则可以通过。 有 $k$ 个点上面有按钮 $s_i$。 你现在位于 $1$ 号点。每次，你可以做两件事情中的一件： 1. 移动。移到相邻的一个点上，注意这条边一定是可以通行的。 2. 按开关。此时，全部路的边权取反。即：$w = 0$ 变成 $1$，$w = 1$ 变成 $0$。 请问你是否能够到达 $n$ 号点。如果可以，求出最少移动次数。 translated by @[liangbowen](https://www.luogu.com.cn/user/367488). 【输入格式】 第一行三个数 $n, m, k$。 接下来 $m$ 行，每行三个数 $u_i, v_i, w_i$表示一条连接 $u_i$ 与 $v_i$ 的边。 最后一行 $k$ 个数，表示按钮的位置。 【输出格式】 如果无法到达，输出 $-1$。否则输出最少移动次数。 【数据范围】 $2 \le n \le 2 \times 10^5$ $1 \le m \le 2 \times 10^5$ $1 \le k \le n$ 保证 $1 \le u_i, v_i \le n$，且 $u_i \ne v_i$。 保证 $1 \le s_1 < s_2 < \cdots < s_k \le n$。

[problemUrl]: https://atcoder.jp/contests/abc277/tasks/abc277_e $ N $ 個の頂点と $ M $ 本の辺からなる無向グラフが与えられます。 $ i\ =\ 1,\ 2,\ \ldots,\ M $ について、$ i $ 番目の辺は頂点 $ u_i $ と頂点 $ v_i $ を結ぶ無向辺であり、 $ a_i\ =\ 1 $ ならばはじめは通行可能、$ a_i\ =\ 0 $ ならばはじめは通行不能です。 また、頂点 $ s_1 $ 、頂点 $ s_2 $ 、$ \ldots $ 、頂点 $ s_K $ の $ K $ 個の頂点にはスイッチがあります。 高橋君は、はじめ頂点 $ 1 $ におり、「下記の**移動**と**スイッチを押す**の $ 2 $ つの行動のどちらかを行うこと」を好きなだけ繰り返します。 - **移動** : いまいる頂点と通行可能な辺を介して隣接する頂点を $ 1 $ つ選び、その頂点に移動する。 - **スイッチを押す** : いまいる頂点にスイッチがあるならば、そのスイッチを押す。その結果、グラフ上のすべての辺の通行可能・通行不能の状態が反転する。すなわち、通行可能である辺は通行不能に、通行不能である辺は通行可能に変化する。 高橋君が頂点 $ N $ に到達することが可能かどうかを判定し、可能な場合は頂点 $ N $ に到達するまでに行う**移動**の回数としてあり得る最小値を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ u_1 $ $ v_1 $ $ a_1 $ $ u_2 $ $ v_2 $ $ a_2 $ $ \vdots $ $ u_M $ $ v_M $ $ a_M $ $ s_1 $ $ s_2 $ $ \ldots $ $ s_K $

高橋君が頂点 $ N $ に到達することが不可能な場合は $ -1 $ を、 可能な場合は頂点 $ N $ に到達するまでに行う**移動**の回数としてあり得る最小値を出力せよ。

5 5 2
1 3 0
2 3 1
5 4 1
2 1 1
1 4 0
3 4

5

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

-1

### 制約 - $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ M\ \leq\ 2\ \times\ 10^5 $ - $ 0\ \leq\ K\ \leq\ N $ - $ 1\ \leq\ u_i,\ v_i\ \leq\ N $ - $ u_i\ \neq\ v_i $ - $ a_i\ \in\ \lbrace\ 0,\ 1\rbrace $ - $ 1\ \leq\ s_1\ \lt\ s_2\ \lt\ \cdots\ \lt\ s_K\ \leq\ N $ - 入力はすべて整数 ### Sample Explanation 1 高橋君は、下記の手順で行動することで頂点 $ N $ に到達できます。 - 頂点 $ 1 $ から頂点 $ 2 $ に移動する。 - 頂点 $ 2 $ から頂点 $ 3 $ に移動する。 - 頂点 $ 3 $ にあるスイッチを押す。これによって、グラフ上のすべての辺の通行可能・通行不能の状態が反転する。 - 頂点 $ 3 $ から頂点 $ 1 $ に移動する。 - 頂点 $ 1 $ から頂点 $ 4 $ に移動する。 - 頂点 $ 4 $ にあるスイッチを押す。これによって、グラフ上のすべての辺の通行可能・通行不能の状態が再び反転する。 - 頂点 $ 4 $ から頂点 $ 5 $ に移動する。 この手順における移動の回数は $ 5 $ 回であり、これが考えられる最小の回数です。 ### Sample Explanation 2 与えられるグラフは、連結でないことや、多重辺を含むことがあります。 この入力例では、高橋君はどのように行動しても頂点 $ N $ に到達することはできないので、$ -1 $ を出力します。