分块思想+最短路
发现对于步长小的doge会连出很多边，很容易导致大量的重边，于是对doge们根据步长分块讨论：根据步长建出分层图，然后把步长不超过某个值的doge们连到对应层上的点上，其余的doge暴力连边，最后在分层图的每层中间把边连满然后跑最短路，这样边数是$O(n$ $sqrt(n))$的
注意：此题数据非常辣鸡，如果确定算法是对的然后被卡了可以问候一下出题人然后摸走，没啥调的必要，主要体现在：
1.只对步长为1的doge们建分层图，然后其余doge们暴力连边，会跑的飞起(吊打“正常”连法)
2.上文的“正常”是指将块大小与$100$取min，不然会连爆。那为什么是和$100$取min呢？因为试出来是这样的，呵呵
3.不知道数据怎么造的，好像太**稀疏了，以至于队列优化的Bellman-Ford跑的比Dijkstra还快，甚至Dijkstra会被卡常
心里默默问候无良出题人
// luogu-judger-enable-o2
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,M=,inf=0x3f3f3f3f;
struct a{int node,dist;};
bool operator <(a x,a y)
{
return x.dist>y.dist;
}
priority_queue<a> hp;
int n,m,c,t1,t2,st,ed,cnt,sqr;
int dis[N],vis[N],val[*M];
int p[N],noww[*M],goal[*M];
void link(int f,int t,int v)
{
noww[++cnt]=p[f],p[f]=cnt;
goal[cnt]=t,val[cnt]=v;
}
void Dijkstra()
{
register int i;
memset(dis,0x3f,sizeof dis);
hp.push((a){st,}),dis[st]=;
while(!hp.empty())
{
a tt=hp.top(); hp.pop(); int tn=tt.node;
if(vis[tn]) continue; vis[tn]=true;
for(i=p[tn];i;i=noww[i])
if(dis[goal[i]]>dis[tn]+val[i])
{
dis[goal[i]]=dis[tn]+val[i];
hp.push((a){goal[i],dis[goal[i]]});
}
}
}
int main ()
{
register int i,j;
scanf("%d%d",&n,&m),sqr=min((int)sqrt(n),);
for(i=;i<=m;i++)
{
scanf("%d%d",&t1,&t2),t1++;
if(i==) st=t1; if(i==) ed=t1;
if(t2<=sqr)
link(t1,t2*n+t1,);
else
{
for(j=t1-t2,c=;j>=;j-=t2,c++) link(t1,j,c);
for(j=t1+t2,c=;j<=n;j+=t2,c++) link(t1,j,c);
}
}
for(i=;i<=sqr;i++)
for(j=;j<=n;j++)
{
if(j-i>=) link(i*n+j,i*n+j-i,);
if(j+i<=n) link(i*n+j,i*n+j+i,);
link(i*n+j,j,);
}
Dijkstra(); dis[ed]==inf?printf("-1"):printf("%d",dis[ed]);
return ;
}