/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
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 に到達するまでに行う移動の回数としてあり得る最小値を出力してください。
制約
- 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
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
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 に到達するまでに行う移動の回数としてあり得る最小値を出力せよ。
入力例 1
5 5 2 1 3 0 2 3 1 5 4 1 2 1 1 1 4 0 3 4
出力例 1
5
高橋君は、下記の手順で行動することで頂点 N に到達できます。
- 頂点 1 から頂点 2 に移動する。
- 頂点 2 から頂点 3 に移動する。
- 頂点 3 にあるスイッチを押す。これによって、グラフ上のすべての辺の通行可能・通行不能の状態が反転する。
- 頂点 3 から頂点 1 に移動する。
- 頂点 1 から頂点 4 に移動する。
- 頂点 4 にあるスイッチを押す。これによって、グラフ上のすべての辺の通行可能・通行不能の状態が再び反転する。
- 頂点 4 から頂点 5 に移動する。
この手順における移動の回数は 5 回であり、これが考えられる最小の回数です。
入力例 2
4 4 2 4 3 0 1 2 1 1 2 0 2 1 1 2 4
出力例 2
-1
与えられるグラフは、連結でないことや、多重辺を含むことがあります。 この入力例では、高橋君はどのように行動しても頂点 N に到達することはできないので、-1 を出力します。
Score : 500 points
Problem Statement
You are given an undirected graph consisting of N vertices and M edges.
For i = 1, 2, \ldots, M, the i-th edge is an undirected edge connecting vertex u_i and v_i that is initially passable if a_i = 1 and initially impassable if a_i = 0.
Additionally, there are switches on K of the vertices: vertex s_1, vertex s_2, \ldots, vertex s_K.
Takahashi is initially on vertex 1, and will repeat performing one of the two actions below, Move or Hit Switch, which he may choose each time, as many times as he wants.
- Move: Choose a vertex adjacent to the vertex he is currently on via an edge, and move to that vertex.
- Hit Switch: If there is a switch on the vertex he is currently on, hit it. This will invert the passability of every edge in the graph. That is, a passable edge will become impassable, and vice versa.
Determine whether Takahashi can reach vertex N, and if he can, print the minimum possible number of times he performs Move before reaching vertex N.
Constraints
- 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
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
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
Output
If Takahashi cannot reach vertex N, print -1; if he can, print the minimum possible number of times he performs Move before reaching vertex N.
Sample Input 1
5 5 2 1 3 0 2 3 1 5 4 1 2 1 1 1 4 0 3 4
Sample Output 1
5
Takahashi can reach vertex N as follows.
- Move from vertex 1 to vertex 2.
- Move from vertex 2 to vertex 3.
- Hit the switch on vertex 3. This inverts the passability of every edge in the graph.
- Move from vertex 3 to vertex 1.
- Move from vertex 1 to vertex 4.
- Hit the switch on vertex 4. This again inverts the passability of every edge in the graph.
- Move from vertex 4 to vertex 5.
Here, Move is performed five times, which is the minimum possible number.
Sample Input 2
4 4 2 4 3 0 1 2 1 1 2 0 2 1 1 2 4
Sample Output 2
-1
The given graph may be disconnected or contain multi-edges. In this sample input, there is no way for Takahashi to reach vertex N, so you should print -1.