洛谷 5608.「YunoOI 2015」我回来了

不知道是什么算法的就归到乱搞里面吧……
看来是个水题?

考虑 BFS 预处理出所有点对之间的最短路,然后令 \(f_{x,y}\) 为和 \(x\) 的最短路不大于 \(y\) 的点的集合,用 bitset 维护。
然后询问的话就是取并集。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <cstdio>
#include <cstring>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
const int N = 1e3;
const int M = 1e5;
int n,m,Q;
vector<int> e[N + 5];
int q[N + 5],head,tail;
int dis[N + 5];
bitset<N + 5> f[N + 5][N + 5],ans;
void bfs(int s)
{
memset(dis,0x3f,sizeof dis),head = tail = 0,dis[q[++tail] = s] = 0;
for(register int p;head < tail;)
{
p = q[++head];
for(register vector<int>::iterator it = e[p].begin();it != e[p].end();++it)
if(dis[*it] > dis[p] + 1)
dis[*it] = dis[p] + 1,q[++tail] = *it;
}
for(register int i = 1;i <= n;++i)
dis[i] <= n && (f[s][dis[i]][i] = 1,1);
for(register int i = 1;i <= n;++i)
f[s][i] |= f[s][i - 1];
}
int main()
{
scanf("%d%d%d",&n,&m,&Q);
for(int u,v;m;--m)
scanf("%d%d",&u,&v),e[u].push_back(v),e[v].push_back(u);
for(register int i = 1;i <= n;++i)
bfs(i);
for(int a,x,y;Q;--Q)
{
ans.reset(),scanf("%d",&a);
for(;a;--a)
scanf("%d%d",&x,&y),ans |= f[x][min(y,n)];
printf("%d\n",ans.count());
}
}