题目描述
有一天，牛牛找到了一个巨大的洞穴。洞穴可以描述成一个有向图，一共有 $N$ 个节点（从 $1$ 到 $N$ 编号）和 $M$ 条长度为 $1$ 的有向边，每条边从某一个节点 $u$ 连向另一个节点 $v$（$u$ 可能等于 $v$）。
为了更好的探索洞穴，牛牛向你提出了 $Q$ 个问题，每个问题给定两个节点 $a, \ b$ 以及一个数 $l$, 你需要告诉牛牛是否存在一条开始于 $a$，结束于 $b$ 的路径，总长度为 $l$。（路径中可以经过任意点、边多次，但只能沿着单向边给定的方向行走，不允许反向行走）。
输入输出
第一行两个数 $N, \ M$ 代表点数和边数
接下来 $M$ 行每行两个整数 $ u_i,\ v_i$ 代表第 $i$ 条边从 $u_i$ 连向 $v_i$，长度为 $1$
接下来一个整数 $Q$ 代表牛牛的问题数
接下来 $Q$ 行每行三个整数 $l_i,\ a_i,\ b_i$ 代表牛牛的一个询问
$20\%$的数据, $1 \leq M \leq 30,\ 1 \leq l_i \leq 5$
$50\%$的数据, $1 \leq li \leq 100$
$100\%$的数据, $1 \leq N \leq 100,\ 1 \leq M \leq 10000,\ 1 \leq Q \leq 1000,\ 1 \leq l_i \leq 10^9 ,\ 1 \leq a_i, b_i, u_i, v_i \leq N$
思路
一开始，没看清楚数据范围的我心态崩了。
看到数据范围后，想到使用倍增和 $bitset$，维护从一个点出发能达到的点数。那就。。。基本等同于暴力了。
代码
#include <bits/stdc++.h>
#define maxn 101
std::bitset<maxn>p[maxn][32];
std::bitset<maxn>now,next;
int n,m,q;
int main(){
scanf("%d%d",&n,&m);
for (register int i=1,a,b;i<=m;++i)
scanf("%d%d",&a,&b),p[a][0][b]=1;
for (register int k=1;k<32;++k)
for (register int i=1;i<=n;++i)
for (register int j=1;j<=n;++j)
if (p[i][k-1][j]) p[i][k]|=p[j][k-1];
scanf("%d",&q);
for (register int i=1,l,x,y;i<=q;++i){
scanf("%d%d%d",&l,&x,&y);
now.reset();now[x]=1;
for (register int j=31;~j;--j){
if (!(l&(1<<j))) continue;
next.reset();
for (register int i=1;i<=n;++i)
if (now[i]) next|=p[i][j];
now=next;
}
puts(now[y]?"YES":"NO");
}
}