[BZOJ4152][AMPPZ2014]TheCaptain

#include
#include
#include
#include
#include
#define N 200010
#define M 800010
#include
#define inf 1e10
using namespace std;
struct dij
{
int u,dis;
bool operator <(const dij &a) const
{
return dis > a.dis;
}
};
struct point
{
int x,y,id;
}p[N];
int head[N],nxt[M],to[M],val[M],dis[N];
int n,cnt;
void add(int u,int v,int w)
{
cnt++;
nxt[cnt] = head[u];
head[u] = cnt;
val[cnt] = w;
to[cnt] = v;
}
bool vis[N];
void dijkstra(int s)
{
memset(dis,127,sizeof(dis));
dis[s] = 0;
priority_queueq;
dij top,qwq;
top.u = s;
top.dis = 0;
q.push(top);
while(q.size())
{
top = q.top();
q.pop();
int u = top.u;
if(vis[u]) continue;
vis[u] = 1;
for(int i = head[u];i;i = nxt[i])
{
int v = to[i];
if(u == v) continue;
if(dis[v] > dis[u] + val[i])
{
dis[v] = dis[u] + val[i];
qwq.u = v;
qwq.dis = dis[v];
q.push(qwq);
}
}
}
return;
}
bool cmp1(point a,point b)
{
if(a.x == b.x) return a.y > b.y;
return a.x > b.x;
}
bool cmp2(point a,point b)
{
if(a.y == b.y) return a.x > b.x;
return a.y > b.y;
}
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;i++)
{
scanf("%d %d",&p[i].x,&p[i].y);
p[i].id = i;//排序后编号会变，用id存下每个点之前的编号
}
sort(p + 1,p + 1 + n,cmp1);
for(int i = 1;i )
{
add(p[i].id,p[i + 1].id,p[i].x - p[i + 1].x);
add(p[i + 1].id,p[i].id,p[i].x - p[i + 1].x);
}
sort(p + 1,p + 1 + n,cmp2);
for(int i = 1;i )
{
add(p[i].id,p[i + 1].id,p[i].y - p[i + 1].y);
add(p[i + 1].id,p[i].id,p[i].y - p[i + 1].y);
}
dijkstra(1);
printf("%d\n",dis[n]);
}