CF原题链接

vjudge原题链接

主要通过分层图实现奇偶分类，跟题解也对过了，CF 上 WA on test 15 case 10000。求条。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf=1e18;
const int N=1e6+5;
vector<int> g[N];
queue<int> q1;
int dis1[N];
int n,m,d;
void bfs1(){
	//处理机器人
	while(!q1.empty()){
		int k=q1.front();
		q1.pop();
		for(int v:g[k]){
			if(dis1[v]>dis1[k]+1 and dis1[k]+1<=d){
				dis1[v]=dis1[k]+1;
				q1.push(v);
			}
		}
	}
}

queue<int> q2;
int dis2[N];
int pre[N];
void bfs2(){
	q2.push(1);
	while(!q2.empty()){
		int k=q2.front();
		q2.pop();
		for(int i:g[k]){
			if((dis2[k]+1<dis1[i] or dis1[i]==inf) and dis2[i]==inf){
				dis2[i]=dis2[k]+1;
				pre[i]=k;
				q2.push(i);
			}
		}
	}
}


vector<int> ans; 
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		cin>>n>>m>>d;
		
		ans.clear();
		for(int i=0;i<=2*n;i++){
			g[i].clear();
		}
		while(!q1.empty()) q1.pop();
		while(!q2.empty()) q2.pop();
		for(int i=1;i<=2*n;i++){
			dis1[i]=inf;
			dis2[i]=inf;
			pre[i]=-1;
		}
		
		for(int i=1;i<=m;i++){
			int x,y;
			cin>>x>>y;
			g[x].push_back(y+n);
			g[y].push_back(x+n);
			g[x+n].push_back(y);
			g[y+n].push_back(x);
		}
		
//		cout<<"robot\n";
		int k;
		cin>>k;
		for(int i=1;i<=k;i++){
			int s;
			cin>>s;
			if(dis1[s]==inf){
				q1.push(s);
				dis1[s]=0;
			}
			
		}
		bfs1();
		dis2[1]=0;
		bfs2();
		if(min(dis2[n],dis2[n+n])==inf){
			cout<<"-1\n";
			continue;
		}
		int p=(dis2[n]<dis2[n+n] ? n : n+n);
		while((p)!=1 and (p-n)!=1){
			ans.push_back((p > n ? p-n : p));
			p=pre[p];
		}
		cout<<min(dis2[n],dis2[n+n])<<"\n";
		reverse(ans.begin(),ans.end());
		cout<<"1 ";
		for(int i:ans){
			cout<<i<<" ";
		}
		cout<<"\n";
		
	}
}