我們是想跑最短路的
我們有兩種建圖方式：
1.對于每個doge i，連向B[j]==B[i]+P[i]*k ,k=..,-2,-1,0,1,2,... ，邊權=|k|，這樣連的複雜度是$O(Nsumlimits_{i=1}^{m}frac{1}{P[i]})$
2.對于每個樓i，建max(P[i])個點，表示可以有一個doge經過這個樓來跳j個距離，也就是說，給P[i][j]連向P[i-j][j]和P[i+j][j]，邊權=1，而且還要給所有的P[i]連起來，邊權是0.
這樣連的複雜度是$O(Nsumlimits_{i=1}^{m}P[i])$，其中P[i]是互不相同的（相同就不加了）
然而都過不了
然後我們發現，複雜度一個是乘P[i]，一個是除以P[i]，這就啟發我們采用分塊的思想，對于P[i]大于$sqrt{N}$的使用第1種建法，小于的使用第二種建法，整體的複雜度就變成$O(Nsqrt{N})$了
然而因為玄學的常數問題，我們需要：
1.讓那個分塊的邊界取$min(sqrt{N},100)$（我也不知道為什麼）
2.在做最短路的時候再計算邊，而不是提前都建好
3.深吸一口氧氣（必要）
4.使用spfa而不是dijkstra（我也不知道為什麼，但我還是用了dijkstra，然後就挂了...）
（代碼寫一年還寫得巨醜）
1 #include<bits/stdc++.h>
2 #define pa pair<int,int>
3 #define lowb(x) ((x)&(-(x)))
4 #define REP(i,n0,n) for(i=n0;i<=n;i++)
5 #define PER(i,n0,n) for(i=n;i>=n0;i--)
6 #define MAX(a,b) ((a>b)?a:b)
7 #define MIN(a,b) ((a<b)?a:b)
8 #define CLR(a,x) memset(a,x,sizeof(a))
9 #define rei register int
10 using namespace std;
11 typedef long long ll;
12 const int maxn=30030,sqrtn=200;
13
14 inline ll rd(){
15 ll x=0;char c=getchar();int neg=1;
16 while(c<'0'||c>'9'){if(c=='-') neg=-1;c=getchar();}
17 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
18 return x*neg;
19 }
20
21 struct Node{
22 int x,y,d;bool isp;
23 Node (int a,int b,int c,bool s){x=a,y=b,d=c,isp=s;}
24 }S=Node(0,0,0,0);
25 int N,SN,M,B[maxn],P[maxn];
26 int dis[maxn*sqrtn],poi[maxn][2],ph[maxn];
27 bool flag[maxn*sqrtn];
28 priority_queue<Node,vector<Node>,greater<Node> > q;
29
30 bool operator > (Node a,Node b){return a.d>b.d;}
31 inline int id(Node a){return a.isp?a.x:M+1+a.x+a.y*N;}
32 inline void print(int x,Node a){printf("Node%d:%d %d %d %d
",x,a.x,a.y,a.d,a.isp);}
33
34 inline int dijkstra(){
35 memset(dis,127,sizeof(dis));
36 dis[id(S)]=0;q.push(S);
37 while(!q.empty()){
38 Node p=q.top();q.pop();
39 if(((!p.isp)&&p.x==B[1])||(p.isp&&p.x==1)) return p.d;
40 if(flag[id(p)]) continue;
41
42 if(!p.isp){
43 for(int i=ph[p.x];i!=-1;i=poi[i][1]){
44 if(P[poi[i][0]]>SN){
45 if(dis[poi[i][0]]<=p.d) continue;
46 dis[poi[i][0]]=p.d;
47 q.push(Node(poi[i][0],0,p.d,1));
48 }else if(P[poi[i][0]]!=p.y){
49 Node x=Node(p.x,P[poi[i][0]],p.d,0);
50 if(dis[id(x)]<=p.d) continue;
51 dis[id(x)]=p.d;q.push(x);
52 }
53 }
54 if(p.y){
55 Node xx=Node(p.x+p.y,p.y,p.d+1,0);
56 if(p.x+p.y<N&&dis[id(xx)]>p.d+1){
57 dis[id(xx)]=p.d+1;
58 q.push(xx);
59 }xx.x=p.x-p.y;
60 if(p.x-p.y>=0&&dis[id(xx)]>p.d+1){
61 dis[id(xx)]=p.d+1;
62 q.push(xx);
63 }
64 }
65 }
66 else{
67 for(int i=B[p.x]+P[p.x],j=1;i<N;i+=P[p.x],j++){
68 Node a=Node(i,0,p.d+j,0);
69 if(dis[id(a)]>p.d+j){
70 dis[id(a)]=p.d+j;q.push(a);
71 }
72 }
73 for(int i=B[p.x]-P[p.x],j=1;i>=0;i-=P[p.x],j++){
74 Node a=Node(i,0,p.d+j,0);
75 if(dis[id(a)]>p.d+j){
76 dis[id(a)]=p.d+j;q.push(a);
77 }
78 }
79 }
80 flag[id(p)]=1;
81 }return -1;
82 }
83
84 int main(){
85 //freopen(".in","r",stdin);
86 rei i,j,k;
87 N=rd(),M=rd();SN=min(100,(int)sqrt(N));
88 memset(ph,-1,sizeof(ph));
89 for(i=0;i<M;i++){
90 B[i]=rd(),P[i]=rd();
91 poi[i][0]=i;poi[i][1]=ph[B[i]];ph[B[i]]=i;
92 }S=Node(B[0],0,0,0);
93 printf("%d
",dijkstra());
94 return 0;
95 }