nzhtl1477-ただいま帰りました
题目描述
珂学题意：
你是威廉！你要做黄油蛋糕给珂朵莉吃~！
68号岛有n个商店，有的商店直接有小路连接，小路的长度都为1
格里克告诉了你哪些地方可能有做黄油蛋糕的原料
但是那个人是个坑货，所以
他会告诉你一些商店，然后告诉你距离这些商店距离<= k的商店中都是可能有原料的
然后你要把这些可能的商店每个都去一遍
你想知道你要去多少个商店
由于你是勇者，所以有m次询问
简洁题意：
给你一个图，每次查询的时候给一堆特殊点以及一个数k，求图中有多少点距离至少一个特殊点距离不超过k
边是无向的
输入输出格式
输入格式：
第一行三个数表示n，m，q
之后m行每行两个数x，y表示这两个点之间连有一条边~
之后q次询问，每个询问先给你一个数a和一个数k
之后一行a个数，表示a个特殊点
输出格式：
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
输出样例#1： 复制
3
2
4
3
4
4
说明
对于30%的数据，n，m，q <= 100，每次查询只给一个点
对于另外30%的数据，k=1
对于100%的数据，n，m，q <= 5000 , a的和<= 500000
解析
在线操作；将每一个点加入队列中间，类似修改了的spfa算法；
同时将几个点加入，就可以将剩下的点按照离他们最近的中心点的距离计算出来；
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rint register int inline int read(){
int x=,f=;char ch=getchar();
while(!isdigit(ch)) f=(ch==),ch=getchar();
while( isdigit(ch)) x=(x<<)+(x<<)+(ch^),ch=getchar();
return f?(~x+):x;
} #define man 5050 struct edge{ int next,to;}e[man<<];
int head[man<<],num=; inline void add(int from,int to){
e[++num]=(edge){head[from],to};
head[from]=num;
} int n,m,q;
int dis[man],vis[man],tot,k; int main(){
memset(dis,,sizeof(dis));
n=read();m=read();q=read();
for(rint i=,x,y;i<=m;i++){
x=read();y=read();
add(x,y);add(y,x);
}
for(rint i=,cnt;i<=q;i++){
queue<int>q;tot=;
memset(vis,,sizeof(vis));
memset(dis,,sizeof(dis));
cnt=read();k=read();
for(rint x,i=;i<=cnt;i++){
x=read();
q.push(x);dis[x]=;vis[x]=;
}
do{
int u=q.front();q.pop();
for(rint i=head[u];i;i=e[i].next){
int to=e[i].to;
dis[to]=min(dis[to],dis[u]+);
if(!vis[to]) vis[to]=,q.push(to);
}
}while(q.size());
for(rint i=;i<=n;i++)
if(dis[i]<=k) tot++;
printf("%d\n",tot);
}
return ;
}