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 intinline int read(){int x=0,f=0;char ch=getchar();while(!isdigit(ch)) f=(ch==45),ch=getchar();while( isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();return f?(~x+1):x; }#define man 5050struct edge{ int next,to;}e[man<<1]; int head[man<<1],num=0;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,63,sizeof(dis));n=read();m=read();q=read();for(rint i=1,x,y;i<=m;i++){x=read();y=read();add(x,y);add(y,x);}for(rint i=1,cnt;i<=q;i++){queue<int>q;tot=0;memset(vis,0,sizeof(vis));memset(dis,63,sizeof(dis));cnt=read();k=read();for(rint x,i=1;i<=cnt;i++){x=read();q.push(x);dis[x]=0;vis[x]=1;}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]+1);if(!vis[to]) vis[to]=1,q.push(to);}}while(q.size());for(rint i=1;i<=n;i++)if(dis[i]<=k) tot++; printf("%d\n",tot);}return 0; }

?

轉載于:https://www.cnblogs.com/Slager-Z/p/9889457.html

總結

以上是生活随笔為你收集整理的nzhtl1477-ただいま帰りました ( bfs )的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。