BZOJ 4152: [AMPPZ2014]The Captain

Description

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

\(n\leqslant 2\times 10^5,x_i,y_i\leqslant 10^9\)

Solution

最短路.

首先如果\(x\)坐标起贡献,那么将所有点按\(x\)坐标排序,他满足\(x_i-x_{i-1}\leqslant x_{i+1}-x_{i-1}\)

所以只需要连排序后相邻的两个点即可,\(y\)轴同理.最后跑Dijstra...

Code

/**************************************************************
    Problem: 4152
    User: BeiYu
    Language: C++
    Result: Accepted
    Time:6128 ms
    Memory:24768 kb
****************************************************************/
 
#include 
using namespace std;
 
#define mpr make_pair
#define uor(i,j,k) for(int i=j;i<=(int)k;i++)
#define dor(i,j,k) for(int i=j;i>=(int)k;i--)
 
typedef long long ll;
typedef pair pr;
const int N = 200500;
 
inline int in(int x=0,char ch=getchar()) { while(ch>'9'||ch<'0') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x; }
 
struct Point { int x,y,id; }p[N];
int cmpx(const Point &a,const Point &b) { return a.xb.d; }
 
int n;
bool b[N];
ll d[N];
vector g[N];
ll get_d(Point a,Point b) { return min(abs(a.x-b.x),abs(a.y-b.y)); }
void AddEdge(int u,int v,ll d) {
    g[u].push_back((Edge){ v,d });
    g[v].push_back((Edge){ u,d });
}
priority_queue q;
ll Dijstra(int s) {
    memset(d,0x3f,sizeof(d));
    memset(b,0,sizeof(b));
    d[s]=0,q.push((Edge) { s,0 });
    for(;!q.empty();) {
        int x=q.top().to;q.pop();
        if(b[x]) continue;b[x]=1;
        uor(i,0,g[x].size()-1) {
            int v=g[x][i].to;
            if(d[x]+g[x][i].d