题面

小J进入了一个迷宫，其由N个房间M条无向边组成

每条边如果状态值为0时，不可通行，如果为1则可通行

比外小J还知道，在K个房间中全局的开关，触动开关，将对整个迷宫所有边的状态

进行一次取反操作.

现在小J想从1号房间走到N号房间，这样就可以逃出生天了......

问最少移动多少步?无解输出-1

Format Input 第一行给出N，M，K

接下来M行，描述边

最后一行给出K个数字，代表有全局开关的房子

2<=N<=2e5

1<=M<=2e5

0<=k<=N

Output 如题

Samples

输入数据 1

5 5 2

1 3 0

2 3 1

5 4 1

2 1 1

1 4 0

3 4

输出数据 1

5

Hint

开始从1走到2

再从2走到3

然后打开3上面的开关

再从3走到1

1走到4

再打开4上面的开关

再从4走到5

代码

#include<bits/stdc++.h>
using namespace std;
struct edge {
	int v, nxt, w;
} e[200030];
struct node {
	int dis, pos;
	bool operator <(const node &x)const {
		return x.dis < dis;
	}
};
priority_queue<node>q;
int head[100010], dis[100010], cnt;
bool vis[100010];
int n, m, k, x;
void add(int u, int v, int w) {
	cnt++;
	e[cnt].nxt = head[u];
	e[cnt].v = v;
	e[cnt].w = w;
	head[u] = cnt;
}

int main() {
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++)dis[i] = 0x7fffffff;
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		if (w == 1)add(u, v, w), add(v, u, w);
		else add(u + n, v + n, 1), add(v + n, u + n, 1);
	}
	for (int i = 1; i <= k; i++) {
		cin >> x;
		add(x, x + n, 0);
		add(x + n, x, 0);
	}

	dis[1] = 0;
	q.push(node{0, 1});
	while (!q.empty()) {
		node t = q.top();
		q.pop();
		int pos = t.pos, w = t.dis;
		if (vis[pos])continue;
		vis[pos] = 1;
		for (int i = head[pos]; i; i = e[i].nxt) {
			int v = e[i].v;
			if (dis[v] > dis[pos] + e[i].w) {
				dis[v] = dis[pos] + e[i].w;
				if (!vis[v]) {
					q.push((node) {
						dis[v], v
					});
				}
			}
		}
	}

	cout << min (dis[n], dis[n + n]);
	return 0;
}