分块思想，机智的建图。
1.n = min(sqrt(N), 100) ……设一个玄学限制，跑得会快很多。
2.SPFA 不要加 LLL 也不要加 SLF 优化！千万不要加！不然九十八！
我写了发 SPFA ，时间略卡。可能 Dijkstra 在这道题会更优秀一些吧……
1 #include <stdio.h> 2 #include <deque> 3 #include <math.h> 4 5 using namespace std; 6 7 const int _V = 30005*105; 8 const int _E = 30005*500; 9 const int INF = 1e9; 10 11 deque<int> Q; 12 int v[_E], w[_E], nxt[_E], fst[_V], dis[_V]; 13 int Tot, N, n, M; 14 bool mk[_V]; 15 16 void Ins(int t1, int t2, int t3) 17 { 18 v[++Tot] = t2, w[Tot] = t3; 19 nxt[Tot] = fst[t1]; 20 fst[t1] = Tot; 21 return; 22 } 23 24 void SPFA(int beg) 25 { 26 int t = (N-1)*(n+1)+n+1, i; 27 for (i = 1; i <= t; ++i) 28 dis[i] = INF, mk[i] = false; 29 while (!Q.empty()) Q.pop_back(); 30 dis[beg] = 0, mk[beg] = true, Q.push_back(beg); 31 while (!Q.empty()) { 32 int p = Q.front(); 33 Q.pop_front(), mk[p] = false; 34 for (i = fst[p]; i; i = nxt[i]) { 35 if (dis[v[i]] > w[i]+dis[p]) { 36 dis[v[i]] = w[i]+dis[p]; 37 if (!mk[v[i]]) { 38 mk[v[i]] = true; 39 Q.push_back(v[i]); 40 } 41 } 42 } 43 } 44 } 45 return; 46 } 47 48 int main() 49 { 50 int i, j, k, beg, end; 51 scanf("%d%d", &N, &M); 52 n = min((int)sqrt(N+0.5), 100); 53 for (i = 0; i < N; ++i) 54 for (j = 1; j <= n; ++j) { 55 Ins(i*(n+1)+j, i*(n+1)+n+1, 0); 56 if (i+j < N) { 57 Ins(i*(n+1)+j, (i+j)*(n+1)+j, 1); 58 Ins((i+j)*(n+1)+j, i*(n+1)+j, 1); 59 } 60 } 61 for (i = 1; i <= M; ++i) { 62 int pos, p; 63 scanf("%d%d", &pos, &p); 64 if (i == 1) beg = pos; 65 else if (i == 2) end = pos; 66 if (p <= n) { 67 Ins(pos*(n+1)+n+1, pos*(n+1)+p, 0); 68 } else { 69 for (j = pos+p; j < N; j += p) 70 Ins(pos*(n+1)+n+1, j*(n+1)+n+1, (j-pos)/p); 71 for (j = pos-p; j >= 0; j -= p) 72 Ins(pos*(n+1)+n+1, j*(n+1)+n+1, (pos-j)/p); 73 } 74 } 75 SPFA(beg*(n+1)+n+1); 76 printf("%d ", dis[end*(n+1)+n+1] >= INF ? -1 : dis[end*(n+1)+n+1]); 77 return 0; 78 }