AT_abc277_e [ABC277E] Crystal Switches

• 题号：AT_abc277_e
• 难度：普及+/提高−（4）
• 标签：广度优先搜索 BFS、图论建模、最短路
• 时间限制：2000 ms
• 内存限制：1024 MB
• 样例数：2
• 提交 / 通过：1284 / 576
• 抓取时间：2026-11-11T08:50:25.062Z
• 正文来源：problem.content（ja）；中文翻译见文末

题目描述

$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$ に到達するまでに行う移動の回数としてあり得る最小値を出力せよ。

样例

样例 1 输入

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

样例 1 输出

5

样例 2 输入

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

样例 2 输出

-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$ を出力します。

中文翻译（洛谷题面翻译）

题目描述

【题面翻译】

给定一张 $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

输入格式

第一行三个数 $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$。

---

由 fetch_luogu_statements.mjs v1.0.0 自动抓取生成；原始数据见 json/AT_abc277_e.json。