本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-11-13 14:24:25

题外话

此题我赛时没做出来，赛后被别人一句话搞懂。

做法

我们把题意略微转化一下：

给定两种类型的边，类型分别为 $1$，$0$。
你只能行走在你状态对应的边上。 例如你的状态是 $1$，就只能走在类型为 $1$ 的边上。
现在有一些节点作为开关。可以在那里切换状态。
问从 $1$ 走到 $n$ 的最短路。

看到有两种边，而且这两种边互不兼容。
而且有开关可以在两种边上切换。
现在瓶颈就在于如何选择是否切换状态。
那么是不是可以将这个“选择”变成一条权值为 $0$ 的边，来进行切换。
而现在有了代表是否选择切换的边，而原图上无法直接从一种边走到另一种边。
可以考虑把两种边分别建图。
而这个代表切换状态的边就是两个图之间的连边。

也就是分层图这个东西。

对种类为 $1$ 的边，所连节点编号为 $1$ 到 $n$。
对于种类为 $0$ 的边，所连节点编号为 $n+1$ 到 $2n$。
对于有开关的节点，设其为 $u$，则连接 $u$ 和 $u+n$。

节点 $n+1$ 到 $2n$ 可以认为是编号为 $1$ 到 $n$ 节点的另一种状态，只不过由于状态不同，这些节点无法通过普通的边，只能通过代表状态切换的边与编号为 $1$ 到 $n$ 互通。

建完图之后跑最短路就行了。

Code

#include <bits\/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int head[maxn*2];
struct EDGE
{
	int to,val,nxt;
}edge[maxn*4];
int cnt;
void add(int u,int to,int val)
{
	edge[++cnt].to=to;
	edge[cnt].val=val;
	edge[cnt].nxt=head[u];
	head[u]=cnt;
}
int n,m,k;
bool vis[maxn*2];
int dis[maxn*2];
void dijkstra()
{
	memset(dis,0x3f3f3f3f,sizeof dis);
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> que;
	que.push(make_pair(0,1));
	dis[1]=0;
	while(!que.empty())
	{
		int u=que.top().second;
		que.pop();
		if(vis[u])continue;
		vis[u]=1;
\/\/		printf("u: %d\n",u);
		for(int i=head[u];i;i=edge[i].nxt)
		{
			int to=edge[i].to;
			if(dis[to]>dis[u]+edge[i].val)
			{
				dis[to]=dis[u]+edge[i].val;
			\/\/	printf("dis[%d]: %d dis[%d]: %d\n",u,dis[u],to,dis[to]);
				que.push(make_pair(dis[to],to));
			}
		}
	}
	int ans=min(dis[n],dis[n*2]);
	if(ans==0x3f3f3f3f)printf("-1");
	else printf("%d",ans);
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	int u,v,a;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&u,&v,&a);
		if(a)
		{
			add(u,v,1);
			add(v,u,1);
		}
		else
		{
			add(u+n,v+n,1);
			add(v+n,u+n,1);
		}
	}
	int si;
	for(int i=1;i<=k;i++)
	{
		scanf("%d",&si);
		add(si,si+n,0);
		add(si+n,si,0);
	}
	dijkstra();
	return 0;
}