BZOJ-4070: [Apio2015]雅加达的摩天楼

[文章目录]

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;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注