L等于1的特殊点(20pts)

• 判断当前点是否是和1好点相连，如果相连就需要提供原材料。

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
bool g[N][N];
int main()
{
    int n,m,q;
    cin>>n>>m>>q;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        g[a][b]=g[b][a]=1;
    }
    while(q--)
    {
        int a,l;
        cin>>a>>l;
        if(g[a][1]) cout<<"Yes"<<endl; //判断a是否和1号点相连，相连就需要提供
        else cout<<"No"<<endl; //否则就不需要提供
    }
	return 0;
}

最短路($O(n+m+q)$)

• 分奇偶判断，如果能够走到，说明遇到提供原材料，这里需要注意，如果存在一套长度为$L$的路径，那么一定有$L+2,L+4....L+6$的路径。

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int N=100010,M=200010;
int n,m,q;
int h[N],e[M],ne[M],idx;
int dist[N][2]; 
//dist[i][0]表示到i偶数条边的最短路 
//dist[i][1]表示到i奇数条边的最短路 
void add(int a,int b) //加边 
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void bfs()
{
	queue<PII> q;
	memset(dist,0x3f,sizeof dist); //初始化距离 
	dist[1][0]=0; //初始化起点 
	q.push({1,0}); //起点入队 
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		for(int i=h[t.x];i!=-1;i=ne[i]) //枚举邻边 
		{
			int x=e[i],y=t.y^1; //终点和终点奇偶 
			if(dist[x][y]>dist[t.x][t.y]+1) //可以更新距离 
			{
				dist[x][y]=dist[t.x][t.y]+1;
				q.push({x,y});
			}
		}
	}
}
int main()
{
    cin>>n>>m>>q;
	memset(h,-1,sizeof h);
	while(m--)
	{
		int a,b;
	    cin>>a>>b;
		add(a,b);
		add(b,a); 
	}
	bfs();
	while(q--)
	{
		int a,l;
		cin>>a>>l;
		if(h[1]==-1) puts("No"); //孤立点 
		else if(l>=dist[a][l&1]) puts("Yes"); //l大于最短距离且奇偶相同 
		else puts("No");
	}
	return 0;
}

宽度优先搜索

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int N=100010,M=200010;
int n,m,q;
vector<int> g[N];
int dist[N][2]; 
//dist[i][0]表示到i偶数条边的最短路 
//dist[i][1]表示到i奇数条边的最短路 
void bfs()
{
	queue<PII> q;
	memset(dist,0x3f,sizeof dist); //初始化距离 
	dist[1][0]=0; //初始化起点 
	q.push({1,0}); //起点入队 
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		for(int i=0;i<g[t.x].size();i++) //枚举邻边 
		{
			int x=g[t.x][i],y=t.y^1; //终点和终点奇偶 
			if(dist[x][y]>dist[t.x][t.y]+1) //可以更新距离 
			{
				dist[x][y]=dist[t.x][t.y]+1;
				q.push({x,y});
			}
		}
	}
}
int main()
{
    cin>>n>>m>>q;
	while(m--)
	{
		int a,b;
	    cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	bfs();
	while(q--)
	{
		int a,l;
		cin>>a>>l;
		if(g[1].size()==0) puts("No"); //孤立点 
		else if(l>=dist[a][l&1]) puts("Yes"); //l大于最短距离且奇偶相同 
		else puts("No");
	}
	return 0;
}