题目描述
珂朵莉给了你一个无向图,每次查询给t个点以及一个常数s,求有多少个图中的点距离给出的那t个点中至少一个距离 <= s

输入描述:
第一行三个数表示n,m,q
之后m行每行两个数u,v表示有一条边位于u和v两个点之间
之后 2 x q 行表示询问
每次询问先输入两个数t,s
之后一行t个数,表示t个特殊点

输出描述:
q行,每行一个数表示答案

示例1
输入

复制
5 6 6
2 3
1 3
2 5
1 3
3 2
2 5
1 1
3
1 1
1
1 4
1
1 2
5
1 4
1
1 4
5
输出
复制

3
2
4
3
4
4
说明
n,m,q<= 5000 ,t的和<= 500000, s <= 1e9


比较经典的多个起点bfs,我们直接每次询问,都把给出的点放到队列当中bfs即可,最后统计答案。


AC代码:

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=5010;
int n,m,q,vis[N],res;
int head[N],nex[N<<1],to[N<<1],tot;
inline void add(int a,int b){
	to[++tot]=b; nex[tot]=head[a]; head[a]=tot;
}
signed main(){
	scanf("%d %d %d",&n,&m,&q);
	while(m--){
		int a,b;	scanf("%d %d",&a,&b),add(a,b),add(b,a);
	}
	while(q--){
		int t,s;	scanf("%d %d",&t,&s);	res=0;	s++;
		memset(vis,0,sizeof vis);	queue<int> q;
		while(t--){
			int x;	scanf("%d",&x),vis[x]=1,q.push(x);
		}
		while(q.size()){
			int u=q.front();	q.pop();
			for(int i=head[u];i;i=nex[i]){
				if(!vis[to[i]])	vis[to[i]]=vis[u]+1,q.push(to[i]);
			}
		}
		for(int i=1;i<=n;i++)	if(vis[i]!=0&&vis[i]<=s)	res++;
		printf("%d\n",res);
	}
	return 0;
}