自动搬运

查看原文

来自洛谷，原作者为

	mrsrz 故障机器人

搬运于2025-08-24 22:19:43，当前版本为作者最后更新于2018-12-10 14:40:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

在太阳西斜的这个世界里，置身天上之森。等这场战争结束之后，不归之人与望眼欲穿的众人， 人人本着正义之名，长存不灭的过去、逐渐消逝的未来。我回来了，纵使日薄西山，即便看不到未来，此时此刻的光辉，盼君勿忘。————世界上最幸福的女孩

珂朵莉，最可爱了呢。

我们定义$f[i][j]$为从点$i$出发，最短路小于等于$j$的点的集合。这个可以用bitset压位存储。

计算$f[i][j]$，我们首先要知道任意两点对间最短路，然后计算出从每个点出发，最短路恰好为$j$的点的集合。然后前缀或一遍就是$f[i][j]$。

计算都可以在$O(\dfrac{n^3}{\omega})$的复杂度内完成。

而求任意点对间最短路，就从每个点开始BFS一遍即可。时间复杂度$O(n(n+m))$。

最后处理询问的时候，就把每个$(x,y)$对应的$f[x][y]$都取并集，然后求其中1的个数即可。时间复杂度$O(\dfrac{n\sum a}{\omega})$。

总时间复杂度$O(n(n+m)+\dfrac{n^3+n\sum a}{\omega})$，空间复杂度$O(\dfrac{n^3}{\omega})$。

然后听说这道题卡前向星

似乎是由于访问连续内存会比较快的原因，用vector存边就跑的飞快，而前向星就T飞了。

Code：

#include<bitset>
#include<cstdio>
#include<cctype>
#include<queue>
#include<vector>
#define N 1003
#ifdef ONLINE_JUDGE
struct istream{
	char buf[23333333],*s;
	inline istream(){
		buf[fread(s=buf,1,23333330,stdin)]='\n';
		fclose(stdin);
	}
	inline istream&operator>>(int&d){
		d=0;
		for(;!isdigit(*s);++s);
		while(isdigit(*s))
		d=(d<<3)+(d<<1)+(*s++^'0');
		return*this;
	}
}cin;
#else
#include<iostream>
using std::cin;
#endif
std::bitset<N>a[N][N];
int n,m,q,dis[N][N];
std::vector<int>G[N];
void bfs(int s,int*dis){
	for(int i=1;i<=n;++i)dis[i]=1002;
	static std::queue<int>q;
	dis[s]=0;
	for(q.push(s);!q.empty();){
		int u=q.front();q.pop();
		for(int i:G[u])
		if(dis[i]==1002){
			dis[i]=dis[u]+1;
			q.push(i);
		}
	}
	for(int i=1;i<=n;++i)
	a[s][dis[i]].set(i);
	for(int i=1;i<=n;++i)a[s][i]|=a[s][i-1];
}
int main(){
	cin>>n>>m>>q;
	while(m--){
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for(int i=1;i<=n;++i)bfs(i,dis[i]);
	while(q--){
		std::bitset<N>ans;
		int x,u,v;
		cin>>x;
		while(x--){
			cin>>u>>v;
			if(v>n)v=n;
			ans|=a[u][v];
		}
		printf("%d\n",ans.count());
	}
	return 0;
}