[文章目录]
Description
印尼首都雅加达市有 N 座摩天楼，它们排列成一条直线，我们从左到右依次将它们编号为 0 到 N−1。除了这 N 座摩天楼外，雅加达市没有其他摩天楼。
有 M 只叫做 “doge” 的神秘生物在雅加达市居住，它们的编号依次是 0 到 M−1。编号为 i 的 doge 最初居住于编号为 Bi 的摩天楼。每只 doge 都有一种神秘的力量，使它们能够在摩天楼之间跳跃，编号为 i 的 doge 的跳跃能力为 Pi （Pi>0）。
在一次跳跃中，位于摩天楼 b 而跳跃能力为 p 的 doge 可以跳跃到编号为 b−p （如果 0≤b−p<N）或 b+p （如果 0≤b+p<N）的摩天楼。
编号为 0 的 doge 是所有 doge 的首领，它有一条紧急的消息要尽快传送给编 号为 1 的 doge。任何一个收到消息的 doge 有以下两个选择:
跳跃到其他摩天楼上；
将消息传递给它当前所在的摩天楼上的其他 doge。
请帮助 doge 们计算将消息从 0 号 doge 传递到 1 号 doge 所需要的最少总跳跃步数，或者告诉它们消息永远不可能传递到 1 号 doge。
大师讲的这一题。
显然是个最短路，但是发现边数过多。考虑去掉没有用的边。将b%p，p相同的放在一起，发现每个b%p+k*p只要相邻的两个doge和其连边即可，边数为O(n/p)。那么对于一个p，b%p的取值只有p个，所以相同的p只会连边O(n)，消耗掉的doge个数为p个。贪心来加doge，只能达到√n个p，所以边数为n√n级别。之后最短路就好了。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,s,t;
struct node
{
int b,p;
}a[30100];
bool cmp(node x,node y){return x.b%x.p==y.b%y.p ? x.b<y.b : x.p < y.p;}
int head[30010],to[9001000],nxt[9001000],date[9001000],cnt;
inline void add(int x,int y,int z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; date[cnt]=z;
}
struct dij
{
int v,dis;
};
bool operator < (dij x,dij y){return x.dis>y.dis;}
int dis[30100];
priority_queue<dij>he;
inline void dijkstra()
{
memset(dis,0x3f,sizeof dis);
dis[s]=0; he.push((dij){s,0}); int x,y;
while(!he.empty())
{
x=he.top().v; y=he.top().dis; he.pop();
if(y>dis[x]) continue;
for(int i=head[x];i;i=nxt[i]) if(dis[to[i]]>y+date[i])
{
dis[to[i]]=y+date[i];
he.push((dij){to[i],dis[to[i]]});
}
}
if(dis[t]==inf) puts("-1");
else printf("%d\n",dis[t]);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i)
scanf("%d%d",&a[i].b,&a[i].p);
s=a[1].b; t=a[2].b;
sort(a+1,a+m+1,cmp); int now=1,end=1,l,r,p;
while(now<=m)
{
while(end<=m && a[end].p==a[now].p && a[end].b%a[end].p==a[now].b%a[now].p) ++end;
l=now; r=now; p=a[now].p;
for(int i=a[now].b%p;i<n;i+=p)
{
while(r<end&&a[r].b<=i) r++;
while(l+1<end&&a[l+1].b<i) l++;
if(r<end&&a[r].b>i) add(a[r].b,i,(a[r].b-i)/p);
if(a[l].b<i) add(a[l].b,i,(i-a[l].b)/p);
}
now=r;
}
dijkstra();
return 0;
}