做dijkstra,但只需要贪心地把每个点连到它左边、右边、上边、下面的第一个点就可以了

 #include<bits/stdc++.h>
#define pa pair<int,int>
#define lowb(x) ((x)&(-(x)))
#define REP(i,n0,n) for(i=n0;i<=n;i++)
#define PER(i,n0,n) for(i=n;i>=n0;i--)
#define MAX(a,b) ((a>b)?a:b)
#define MIN(a,b) ((a<b)?a:b)
#define CLR(a,x) memset(a,x,sizeof(a))
#define rei register int
using namespace std;
typedef long long ll;
const int maxn=2e5+; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} struct Node{
int x,y,id;
}pos[maxn];
int N,xnxt[maxn][],ynxt[maxn][];
int dis[maxn],px[maxn],py[maxn];
bool flag[maxn];
priority_queue<pa,vector<pa>,greater<pa> > q; inline bool cmp1(Node a,Node b){return a.x<b.x;}
inline bool cmp2(Node a,Node b){return a.y<b.y;} inline void psh(int x,int d){
if(dis[x]==-||d<dis[x]){
dis[x]=d;
if(!flag[x]) q.push(make_pair(d,x));
}
} inline void dijkstra(){
memset(dis,-,sizeof(dis));dis[]=;
q.push(make_pair(,));
while(!q.empty()){
int p=q.top().second;q.pop();if(flag[p]) continue;
flag[p]=;
if(p==N) return;
if(xnxt[p][]) psh(xnxt[p][],dis[p]+px[p]-px[xnxt[p][]]);
if(xnxt[p][]) psh(xnxt[p][],dis[p]-px[p]+px[xnxt[p][]]);
if(ynxt[p][]) psh(ynxt[p][],dis[p]+py[p]-py[ynxt[p][]]);
if(ynxt[p][]) psh(ynxt[p][],dis[p]-py[p]+py[ynxt[p][]]);
}
} int main(){
//freopen(".in","r",stdin);
rei i,j,k;
N=rd();
for(i=;i<=N;i++) px[i]=pos[i].x=rd(),py[i]=pos[i].y=rd(),pos[i].id=i;
sort(pos+,pos+N+,cmp1);
for(i=;i<=N;i++){
xnxt[pos[i].id][]=pos[i-].id;
xnxt[pos[i].id][]=pos[i+].id;
}
sort(pos+,pos+N+,cmp2);
for(i=;i<=N;i++){
ynxt[pos[i].id][]=pos[i-].id;
ynxt[pos[i].id][]=pos[i+].id;
}
dijkstra();
printf("%d\n",dis[N]);
return ;
}

最新文章

  1. Group by
  2. hdu2588 GCD (欧拉函数)
  3. 阿里云Linux系统挂载数据盘
  4. codeforces 451E Devu and Flowers
  5. Add Binary &lt;leetcode&gt;
  6. oracle备忘
  7. AFNetworking 原作者都无法解决的问题: 如何使用ip直接访问https网站?
  8. myeclipse2014安装反编译插件
  9. The Best Path---hdu5883(欧拉路径)
  10. eclipse下使用tomcat启动maven项目
  11. ios应用,今年最蛋疼的6月,IPV6!!
  12. LA 4975
  13. hdoj 2717 Catch That Cow【bfs】
  14. git错误:fatal: Not a git repository (or any of the parent directories): .git
  15. perl 爬取数据&lt;1&gt;
  16. 前端入门HTML5扩展知识(一)
  17. 戏说Java多线程
  18. Windows下安装MySQLdb, Python操作MySQL数据库的增删改查
  19. HDU 5833 (2016大学生网络预选赛) Zhu and 772002(高斯消元求齐次方程的秩)
  20. smart beta

热门文章

  1. HO引擎近况20190110
  2. 20155216 实验一 逆向与Bof基础
  3. 20155311 Exp3 免杀原理与实践
  4. # 20155337《网络对抗》Exp6 信息搜集与漏洞扫描
  5. WPF编程,C#中对话框自动关闭的一种方法。
  6. AWK处理数组
  7. 命令行模式和python交互模式
  8. 使用DOS工具修复数据库
  9. mpvue两小时,产出一个《点钞辅助工具》小程序
  10. [转]JVM系列三:JVM参数设置、分析