优化建图是一种思想。

题意

有\(n\)个城市分布在小鸟岛上，有\(m\)个弹弓分布在这些城市里。因为弹弓体积大，固定麻烦，所以每个弹弓只能把小鸟弹飞到一块固定的矩形范围内的城市，同时小鸟会在空中滞留\(t_i\)的时间。闪电黄的家在1号城市，追求速度的它想知道，若只使用弹弓出行，它从家到其他所有城市的最短时间花费是多少。

抱歉魔改了题面，但是这个题意真的太像愤怒的小鸟了好吗

思路

暴力：枚举每两个城市间是否能转移进行建图跑最短路。

太浪费了，这么大的矩形有很多点肯定连不上的呀。根据套路，我们想个数据结构优化建图。

• 二维线段树优化建图
• 树套树优化建图
• K-D tree优化建图

前两个我不会

首先我们把这n个城市建成2-D tree，然后跑Dijkstra:

若当前结点位置在转移的范围内，插入队列，递归查找子节点并更新覆盖范围。

若弹跳的范围与树上结点覆盖的范围有交，查找之，否则不查找。

就这么简单。怎么说K-D tree就是优雅的暴力呢。

实现

我们用一个结构体node存储树上节点信息，用一个结构体data表示一个转移（边）。

对于一个转移，每次从根开始查找，根据以上策略遍历整棵树。时间复杂度O(能过)。事实上，我还跑了目前luogu榜一（醒醒啊你只是因为评测机最近变快了）

把查找单独拉出来：

inline bool cross(node a,data b){return a.l[0]<=b.r[0] and a.r[0]>=b.l[0] and a.l[1]<=b.r[1] and a.r[1]>=b.l[1];}
void solve(node& x,data& p){
    if(!x.del and x.in(p)){//若该点坐标在覆盖范围内
        if(x.id!=1){
            dis[x.id]=p.v;
            for(int i=head[x.id];i;i=nxt[i]){//遍历所有能到的位置
                data u=to[i];
                u.v+=p.v;
                q.push(u);
            }
        }
        x.del=1;//根据dijkstra的贪心策略，该点不再入队
        x.clear();//为了保留结点查询的作用。下面会更新范围
    }
    if(x.son[0]){
        node &now=e[x.son[0]];
        if(cross(now,p)) solve(now,p);//注意这里判断的是矩形是否有交而非城市坐标
        if(x.del) x.copy(now);
        else x.update(now);//更新范围
    }
    if(x.son[1]){
        node &now=e[x.son[1]];
        if(cross(now,p)) solve(now,p);
        if(x.del and !x.son[0]) x.copy(now);
        else x.update(now);//更新范围
    }
}

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
inline int read(){
    int w=0,x=0;char c=getchar();
    while(!isdigit(c))w|=c=='-',c=getchar();
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return w?-x:x;
}
namespace star
{
    const int maxn=7e4+10,maxm=15e4,INF=0x3f3f3f3f;
    int n,m,w,h,root,dis[maxn];
    struct data{
        int v,l[2],r[2];
        inline bool operator < (const data &zp) const{return v>zp.v;}
    };
    int ecnt,head[maxm],nxt[maxm];
    data to[maxm];
    inline void add(int a,data b){
        to[++ecnt]=b,nxt[ecnt]=head[a],head[a]=ecnt;
    }
    struct node{
        int x[2],l[2],r[2],son[2],id;
        static int d;//“只是声明我要用这个变量，但是它现在还不存在”
        bool del;
        inline void clear(){
            for(int i=0;i<2;i++) x[i]=0,l[i]=INF,r[i]=-INF;
        }
        inline void init(int zp){
            for(int i=0;i<2;i++) x[i]=l[i]=r[i]=read();
            id=zp;
        }
        inline void update(const node &zp){
            for(int i=0;i<2;i++) l[i]=min(l[i],zp.l[i]),r[i]=max(r[i],zp.r[i]);
        }
        inline void copy(const node &zp){
            for(int i=0;i<2;i++) l[i]=zp.l[i],r[i]=zp.r[i];
        }
        inline bool operator < (const node &zp) const{return x[d]<zp.x[d];};
        inline bool in(const data &zp) const {return x[0]>=zp.l[0] and x[0]<=zp.r[0] and x[1]>=zp.l[1] and x[1]<=zp.r[1];}
    }e[maxn];
    int node::d;//现在这个变量存在了，并且每个node都会用它
    int build(int l,int r,int d){
        node::d=d;
        int mid=l+r>>1;
        nth_element(e+l,e+mid,e+r+1);
        if(l<mid) e[mid].update(e[e[mid].son[0]=build(l,mid-1,d^1)]);
        if(r>mid) e[mid].update(e[e[mid].son[1]=build(mid+1,r,d^1)]);
        return mid;
    }
    priority_queue<data> q;
    inline bool cross(node a,data b){return a.l[0]<=b.r[0] and a.r[0]>=b.l[0] and a.l[1]<=b.r[1] and a.r[1]>=b.l[1];}
    void solve(node& x,data& p){
        if(!x.del and x.in(p)){
            if(x.id!=1){
                dis[x.id]=p.v;
                for(int i=head[x.id];i;i=nxt[i]){
                    data u=to[i];
                    u.v+=p.v;
                    q.push(u);
                }
            }
            x.del=1;
            x.clear();
        }
        if(x.son[0]){
            node &now=e[x.son[0]];
            if(cross(now,p)) solve(now,p);
            if(x.del) x.copy(now);
            else x.update(now);
        }
        if(x.son[1]){
            node &now=e[x.son[1]];
            if(cross(now,p)) solve(now,p);
            if(x.del and !x.son[0]) x.copy(now);
            else x.update(now);
        }
    }
    inline void work(){
        n=read(),m=read(),w=read(),h=read();
        for(int i=1;i<=n;i++) e[i].init(i);
        root=build(1,n,0);
        memset(dis,INF,sizeof dis);
        dis[1]=0;
        for(int i=1;i<=m;i++){
            data zp;
            int x=read();
            zp.v=read(),zp.l[0]=read(),zp.r[0]=read(),zp.l[1]=read(),zp.r[1]=read();
            add(x,zp);
        }
        for(int i=head[1];i;i=nxt[i]) q.push(to[i]);
        while(!q.empty()){
            data x=q.top();q.pop();
            solve(e[root],x);
        }
        for(int i=2;i<=n;i++) printf("%d\n",dis[i]);
    }
}
signed main(){
    star::work();
    return 0;
}

PS：据银牌学姐推荐，方差建树常数大，K维循环建树虽然有时候会被卡但实际可能比前者优秀。

为啥题面那么喜欢跳蚤用小鸟们不可爱吗owo

自己吃别人嚼过的馒头为啥还敢写题解？因为觉得自己的马蜂太好看了所以来分享一下