分块思想+最短路
发现对于步长小的doge会连出很多边，很容易导致大量的重边，于是对doge们根据步长分块讨论：根据步长建出分层图，然后把步长不超过某个值的doge们连到对应层上的点上，其余的doge暴力连边，最后在分层图的每层中间把边连满然后跑最短路，这样边数是$O(n$ $sqrt(n))$的
注意：此题数据非常辣鸡，如果确定算法是对的然后被卡了可以问候一下出题人然后摸走，没啥调的必要，主要体现在：
1.只对步长为1的doge们建分层图，然后其余doge们暴力连边，会跑的飞起(吊打“正常”连法)
2.上文的“正常”是指将块大小与$100$取min，不然会连爆。那为什么是和$100$取min呢？因为试出来是这样的，呵呵
3.不知道数据怎么造的，好像太**稀疏了，以至于队列优化的Bellman-Ford跑的比Dijkstra还快，甚至Dijkstra会被卡常
心里默默问候无良出题人
1 // luogu-judger-enable-o2 2 #include<cmath> 3 #include<queue> 4 #include<cstdio> 5 #include<cstring> 6 #include<algorithm> 7 using namespace std; 8 const int N=2500005,M=8000005,inf=0x3f3f3f3f; 9 struct a{int node,dist;}; 10 bool operator <(a x,a y) 11 { 12 return x.dist>y.dist; 13 } 14 priority_queue<a> hp; 15 int n,m,c,t1,t2,st,ed,cnt,sqr; 16 int dis[N],vis[N],val[2*M]; 17 int p[N],noww[2*M],goal[2*M]; 18 void link(int f,int t,int v) 19 { 20 noww[++cnt]=p[f],p[f]=cnt; 21 goal[cnt]=t,val[cnt]=v; 22 } 23 void Dijkstra() 24 { 25 register int i; 26 memset(dis,0x3f,sizeof dis); 27 hp.push((a){st,0}),dis[st]=0; 28 while(!hp.empty()) 29 { 30 a tt=hp.top(); hp.pop(); int tn=tt.node; 31 if(vis[tn]) continue; vis[tn]=true; 32 for(i=p[tn];i;i=noww[i]) 33 if(dis[goal[i]]>dis[tn]+val[i]) 34 { 35 dis[goal[i]]=dis[tn]+val[i]; 36 hp.push((a){goal[i],dis[goal[i]]}); 37 } 38 } 39 } 40 int main () 41 { 42 register int i,j; 43 scanf("%d%d",&n,&m),sqr=min((int)sqrt(n),80); 44 for(i=1;i<=m;i++) 45 { 46 scanf("%d%d",&t1,&t2),t1++; 47 if(i==1) st=t1; if(i==2) ed=t1; 48 if(t2<=sqr) 49 link(t1,t2*n+t1,0); 50 else 51 { 52 for(j=t1-t2,c=1;j>=1;j-=t2,c++) link(t1,j,c); 53 for(j=t1+t2,c=1;j<=n;j+=t2,c++) link(t1,j,c); 54 } 55 } 56 for(i=1;i<=sqr;i++) 57 for(j=1;j<=n;j++) 58 { 59 if(j-i>=1) link(i*n+j,i*n+j-i,1); 60 if(j+i<=n) link(i*n+j,i*n+j+i,1); 61 link(i*n+j,j,0); 62 } 63 Dijkstra(); dis[ed]==inf?printf("-1"):printf("%d",dis[ed]); 64 return 0; 65 }