Crystal Switches

题目描述

给你一个由 $N$ 个顶点和 $M$ 条边组成的无向图。
对于 $i = 1, 2, \ldots, M$，第 $i$ 条边是连接顶点 $u_i$ 与 $v_i$ 的无向边，如果 $a_i = 1$ 则该边起始时可通行，如果 $a_i = 0$ 则起始时不可通行。 此外，有开关位于 $K$ 个顶点上：顶点 $s_1$、顶点 $s_2$、$\ldots$、顶点 $s_K$。 Takahashi 起始位于顶点 $1$，并会重复执行下面两种操作之一：Move 或 Hit Switch，他每次可以任选其一，并且可以执行任意多次。

Move：选择一条与他当前所在顶点相邻的边所连的顶点，并移动到该顶点。 Hit Switch：如果他当前所在的顶点上有开关，则按下它。这会反转图中每条边的可通行性。也就是说，可通行的边将变为不可通行，反之亦然。

判断 Takahashi 是否能到达顶点 $N$，如果能，输出到达顶点 $N$ 之前他执行 Move 的最小可能次数。

输入格式

输入从标准输入按照以下格式给出： $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$

输出格式

如果 Takahashi 无法到达顶点 $N$，输出 $-1$； 如果可以，输出到达顶点 $N$ 之前他执行 Move 的最小可能次数。

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$ 输入中的所有值均为整数。Takahashi 可以按如下方式到达顶点 $N$。

从顶点 $1$ 移动到顶点 $2$。 从顶点 $2$ 移动到顶点 $3$。 按下顶点 $3$ 上的开关。这会反转图中每条边的可通行性。 从顶点 $3$ 移动到顶点 $1$。 从顶点 $1$ 移动到顶点 $4$。 按下顶点 $4$ 上的开关。这会再次反转图中每条边的可通行性。 从顶点 $4$ 移动到顶点 $5$。

这里，Move 共执行了五次，这是最小可能次数。
给定的图可能是不连通的或包含多重边。 在这个样例输入中，Takahashi 无法到达顶点 $N$，因此你应该输出 $-1$。

标签: AtCoder|abc277E

来源

AtCoder|abc277E