分数: 500 点
问题陈述
给你一个无向图,包括 N 顶点和 M 边缘。
对于 i = 1, 2, \ldots, M, i-th 边是连接顶点的无向边 u_i 和 v_i 最初是可以通过的,如果 a_i = 1 并且最初无法通行,如果 a_i = 0。
此外,还有开关 K 顶点:顶点 s_1,顶点 s_2, \ldots,顶点 s_K.
高桥最初位于顶点 1,并将重复执行以下两个操作之一, 移动 or 点击开关,他每次都可以选择,可以选择任意多次。
- 移动:通过一条边选择与当前所在顶点相邻的顶点,然后移动到该顶点。
- 点击开关:如果他当前所在的顶点上有一个开关,请点击它。这将反转图中每条边的通过性。也就是说,可以通过的边缘将变得不可通过,反之亦然。
判断Takahashi是否可以到达顶点 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.
此处,Move 执行了五次,这是可能的最小次数。
示例输入 2
4 4 2 4 3 0 1 2 1 1 2 0 2 1 1 2 4
示例输出 2
-1
给定的图形可能是断开的或包含多边。 在此示例输入中,Takahashi 无法到达顶点 N,所以你应该打印 -1.