先到为敬 题解

这tm才 $\color{orange}{橙}$？？？

解题思路

显然是一道最短路，不过难就难在连边上。
发现点数可以达到 $2 \times 10^5$，自然不可能全部连边，否则空间爆炸，考虑启发式连边。

定义 $dis_{X,Y}$，为 点 $X$，$Y$ 之间边的权值。
我们发现，定义 3 个点 $A(a_x,a_y)$，$B(b_x,b_y)$，$C(c_x,c_y)$，当 $a_x \ge b_x \ge c_x$，当三者以 x 的差为边权时，$dis_{A,C}=dis_{A,B}+dis_{B,C}$；同理，当 $a_y \ge b_y \ge c_y$，当三者以 y 的差为边权时，$dis_{A,C}=dis_{A,B}+dis_{B,C}$。
可能这里没有看出什么，但是事实上，意味着我们只需要将自己与自己 x 和 y 分别相邻的 4 个（或者更少）点连边，就可以了。用 sort 排序两遍就可以了。

AC 代码（略显多余）

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
const int N=200005;
int n;
struct dot{
    int x,y,id;
}a[N];
bool cmp1(dot x,dot y){
    return x.x<y.x;
}
bool cmp2(dot x,dot y){
    return x.y<y.y;
}
bool cmp3(dot x,dot y){
    return x.id<y.id;
}
int h[N],e[N<<2],ne[N<<2],w[N<<2],idx;
void add(int a,int b,int c){
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
int cal(int x,int y){
    return min(abs(a[x].x-a[y].x),abs(a[x].y-a[y].y));
}
int dis[N];
int vis[N];
void dijkstra(){
    dis[1]=0;
    priority_queue<PII,vector<PII>,greater<PII> > q;
    q.push({0,1});
    while(q.size()){
        int d=q.top().first;
        int p=q.top().second;
        q.pop();
        if(vis[p])continue;
        vis[p]=1;
        for(int i=h[p];i!=-1;i=ne[i]){
            int j=e[i],v=w[i];
            if(dis[j]>dis[p]+v){
                dis[j]=dis[p]+v;
                q.push({dis[j],j});
            }
        }
    }
}
int main(){
    memset(h,-1,sizeof h);
    memset(dis,0x3f,sizeof dis);
    //ios::sync_with_stdio(0);
    //cin.tie(0);
    //cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y;
        a[i].id=i;
    }
    sort(a+1,a+n+1,cmp1);
    for(int i=1;i<n;){
        int tmp=i;
        i++;
        for(i;a[i].x==a[tmp].x;i++){
            add(a[i].id,a[tmp].id,0);
            //cout<<a[i].id<<" "<<a[tmp].id<<" "<<0<<endl;
            add(a[tmp].id,a[i].id,0);
        }
        int f=cal(i,i-1);
        add(a[i].id,a[i-1].id,f);
        add(a[i-1].id,a[i].id,f);
        //cout<<a[i-1].id<<" "<<a[i].id<<" "<<f<<endl;
    }
    sort(a+1,a+n+1,cmp2);
    for(int i=1;i<n;){
        int tmp=i;
        i++;
        for(i;a[i].y==a[tmp].y;i++){
            add(a[i].id,a[tmp].id,0);
            add(a[tmp].id,a[i].id,0);
            //cout<<a[i].id<<" "<<a[tmp].id<<" "<<0<<endl;
        }
        int f=cal(i,i-1);
        add(a[i].id,a[i-1].id,f);
        add(a[i-1].id,a[i].id,f);
        //cout<<a[i-1].id<<" "<<a[i].id<<" "<<f<<endl;
    }
    sort(a+1,a+n+1,cmp3);
    dijkstra();
    cout<<dis[n];
}

这怎么说都至少是 $\color{green}{绿}$ 吧，dijkstra 本身都是 $\color{yellow}{黄}$ 了。
还是说我大炮轰蚊子了？
$\color{white}{赞美出题人和神奇的评级系统}$