← 返回题目列表

AtCoder · abc277_e

H. 晶体开关

中文机器翻译题面 查看原题

分数: 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.