题目描述

有一天,牛牛找到了一个巨大的洞穴。洞穴可以描述成一个有向图,一共有 $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$,维护从一个点出发能达到的点数。那就。。。基本等同于暴力了。

代码