本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-12 19:34:19

思路

把初始开启的走廊放到一张图上，发现这张图上的简单路径一定能走，所以这张图上 $1$ 到 $n$ 的最短路就是一种方案，设其长度为 $d$。

考虑通过别的方法走到 $n$，发现若 $(1,n)$ 初始关闭，那么走完第一条边后就会开启，只要再走回 $1$ 就可以直接走到 $n$。那么 $1\to x\to y\to 1\to n$ 就是一种路径，其中 $(1,x),(x,y)$ 初始开启，$(y,1),(1,n)$ 初始关闭，长度为 $4$。

由于这已经是最短的初始不完整的路径，所以若最短路长度 $d\le 4$，就可以直接用最短路。

分析这种路径什么时候存在，发现只要有点 $y$ 与点 $1$ 的距离为 $2$，那么就存在 $x$ 使得 $(1,x),(x,y)$ 初始开启，且 $(1,y)$ 初始关闭，否则距离会变为 $1$。同时如果 $(1,n)$ 初始开启，则最短路 $d=1$，不会再用长为 $4$ 的路径，所以 $(1,n)$ 初始关闭，可以确定有这样的路径。

如果没有这种路径，那么初始与 $1$ 号点在同一个连通块中的所有点全都与 $1$ 号点有直接连边，那么先走到 $x$，以 $x$ 为新的起点寻找上一种路径，也就是 $1\to x \to y\to z\to x\to n$，其中 $(z,x),(x,n)$ 初始关闭，其余初始开启，长度为 $5$。

考虑这种路径什么时候存在，发现同上只要有点 $z$ 与点 $x$ 的距离为 $2$ 即可。那么当且仅当所有与 $1$ 连通的点 $x$ 都没有合法的 $z$ 时会无解，也就是连通块内每个点都与其他所有点有连边，即这个连通块子图是完全图。

由于在完全图上每次走边都会使出发点被完全孤立开来，只会让完全图连通块越来越小，所以这种路径也不存在时就可以确定无解了。

具体寻找路径时直接遍历所有的出边即可，时间复杂度的话第一种路径时每条边只会作为 $(x,y)$ 被搜到一次，第二种路径时 $(x,y,z)$ 似乎相当于三元环记数那种复杂度？笔者太菜不会证。

代码

#include<iostream>
#include<vector> 
#include<queue>
using namespace std; 
const int N=3e5+10;
int n,m,fa[N],dis[N],te[N];
vector <int> edge[N]; 
queue <int> q;
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v; cin>>u>>v;
		edge[u].push_back(v),edge[v].push_back(u);
	}
	q.push(n),dis[n]=1;
	while(q.size())
	{
		int u=q.front(); q.pop();
		for(int v:edge[u]) if(!dis[v]) dis[v]=dis[u]+1,fa[v]=u,q.push(v);
	} 
	if(dis[1]&&dis[1]<=5)
	{
		cout<<dis[1]-1<<'\n'; int p=1;
		while(p!=n) cout<<p<<' ',p=fa[p];
		cout<<n; return 0;
	} \/\/原图最短路 
	for(int x:edge[1]) te[x]=1;
	for(int x:edge[1]) for(int y:edge[x]) if(y!=1&&te[y]!=1) 
	{
		cout<<4<<'\n'<<1<<' '<<x<<' '<<y<<' '<<1<<' '<<n;
		return 0;
	} \/\/第一种 
	for(int x:edge[1])
	{
		for(int y:edge[x]) te[y]=x;
		for(int y:edge[x]) if(y!=1) for(int z:edge[y]) if(z!=x&&te[z]!=x)
		{
			cout<<5<<'\n'<<1<<' '<<x<<' '<<y<<' '<<z<<' '<<x<<' '<<n;
			return 0;
		}
	} \/\/第二种 
	cout<<-1;
	return 0;
}