当 j \gt \sqrt{n} 时，只有 m \sqrt{n} 个状态（最多有 m 只 doge，每只 doge 只有 \frac{n}{j}\lt \sqrt{n} 个可行位置）。
状态判重时使用 `std::set` 会 TLE，可以用 hash 或者 `std::bitset`。
时间复杂度 $O((n+m)\sqrt{n})$。
另外原题数据有点水，同时洛谷只取了原题的很少一部分数据所以更水，建议大家去 [UOJ](http://uoj.ac/problem/111) 提交此题以进一步检验程序正确性。
```cpp
#include <queue>
#include <tuple>
#include <bitset>
#include <cstdio>
#include <vector>
#include <algorithm>
const int maxN = 30005;
int N, M, S, T;
std::vector<int> Doge[maxN];
std::queue<std::tuple<int, int, int>> Q;
std::bitset<maxN> vis[maxN];
bool Vis[maxN];
void insert(int i, int p, int step)
{
if (!Vis[i])
{
Vis[i] = true;
for (auto x : Doge[i])
if (!vis[i].test(x))
vis[i].set(x), Q.emplace(i, x, step);
}
if (!vis[i].test(p))
vis[i].set(p), Q.emplace(i, p, step);
}
int main()
{
scanf("%d%d", &N, &M);
for (int i = 0, b, p; i != M; ++i)
{
scanf("%d%d", &b, &p);
if (i == 0)
S = b;
if (i == 1)
T = b;
Doge[b].push_back(p);
}
if (S == T)
{
puts("0");
return 0;
}
Vis[S] = true;
for (auto x : Doge[S])
if (!vis[S].test(x))
{
vis[S].set(x);
Q.emplace(S, x, 0);
}
while (!Q.empty())
{
int i, p, step;
std::tie(i, p, step) = Q.front();
Q.pop();
if (i - p == T || i + p == T)
{
printf("%d\n", step + 1);
return 0;
}
if (i - p >= 0)
insert(i - p, p, step + 1);
if (i + p < N)
insert(i + p, p, step + 1);
}
puts("-1");
return 0;
}
```