这篇文章上次修改于 434 天前，可能其部分内容已经发生变化，如有疑问可询问作者。
本文共 1834 个字，阅读时长 ≈ 5 分钟

BZOJ 4152. The Captain

题目链接

题意

给定平面上的 $n$ 个点，定义 $(x_1,y_1)$ 到 $(x_2,y_2)$ 的费用为 $\min(|x_1-x_2|,|y_1-y_2|)$，求从 $1$ 号点走到 $n$ 号点的最小费用。

思路

很容易发现本题的难点在于如何建图，建好图后直接跑最短路即可。既然题目中提到 $\min(|x_1-x_2|,|y_1-y_2|)$，自然想到可以从此方面入手，考虑将点按照x坐标从小到大排序，然后将排好序的数组按照顺序两两建边，再按照y坐标排序重复操作，跑一遍最短路即可。

进行一个正确性的证明：对于一个点，最优的策略自然是去费用最小的点，也就是x坐标离他最近的或者y坐标离他最近的，那我们进行两次排序并建边，边权为x/y坐标差，跑最短路时只会往x坐标离他最近的或者y坐标离他最近的这两个点跑，自然最后就是最短路。

代码实现时我用了堆优化dijkstra跑单源最短路，但是重载运算符实现小根堆的做法一直出错，最后发现是重载运算符的比较顺序跟我所想的并不一样，这里我改成了 greater<pii>，不过在结构体中重载运算符也是可行的。

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<climits>
using namespace std;
int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return x*f;
}
const int N=200005,inf=INT_MAX>>1;
struct node{
    int x,y,p;
}a[N];
//两次分别按照x和y排序
bool cmp1(node a,node b){
    return a.x<b.x;
}
bool cmp2(node a,node b){
    return a.y<b.y;
}
int n;
int idx=1,head[N],to[N<<2],nxt[N<<2],w[N<<2];
void addedge(int u,int v,int _w){
    to[++idx]=v;
    w[idx]=_w;
    nxt[idx]=head[u];
    head[u]=idx;
}
typedef pair<int,int> pii;
//这里通过greater<pii>改成了小根堆
priority_queue<pii,vector<pii>,greater<pii>> q;
int dis[N];
bool vis[N];
void dij(){
    pii p;
    q.emplace((pii){0,1});
    int u,v,d;
    dis[1]=0;
    while(!q.empty()){
        p=q.top();
        q.pop();
        u=p.second,d=p.first;
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head[u];i;i=nxt[i]){
            v=to[i];
            if(dis[v]>dis[u]+w[i]){
                dis[v]=dis[u]+w[i];
                if(!vis[v]) q.emplace((pii){dis[v],v});
            }
        }
    }
}
int main()
{
    n=read();
    for(int i=0;i<=n;++i) dis[i]=inf;
    for(int i=1;i<=n;++i){
        a[i].x=read();
        a[i].y=read();
        a[i].p=i;
    }
    //排序后加边，边权即为坐标差
    sort(a+1,a+1+n,cmp1);
    for(int i=2;i<=n;++i){
        addedge(a[i-1].p,a[i].p,abs(a[i].x-a[i-1].x));
        addedge(a[i].p,a[i-1].p,abs(a[i].x-a[i-1].x));
    }
    sort(a+1,a+n+1,cmp2);
    for(int i=2;i<=n;++i){
        addedge(a[i-1].p,a[i].p,abs(a[i].y-a[i-1].y));
        addedge(a[i].p,a[i-1].p,abs(a[i].y-a[i-1].y));
    }
    dij();
    printf("%d\n",dis[n]);
    return 0;
}