按照横,竖为方向跑一个最短路即可,算是水题~

#include <bits/stdc++.h>
#define N 200005
#define E 2000000
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int n,m,tot,edges,s,T;
int hd[E],to[E],nex[E],val[E],d[E],done[E],id[E][2];
void addedge(int u,int v,int c)
{
nex[++edges]=hd[u],hd[u]=edges,to[edges]=v,val[edges]=c;
}
struct Point
{
int x,y,id;
Point(int x=0,int y=0):x(x),y(y){}
}t[N];
struct Node
{
int u,dis;
Node(int u=0,int dis=0): u(u),dis(dis){}
bool operator<(Node b) const
{
return b.dis<dis;
}
};
priority_queue<Node>q;
bool cmpx(Point a,Point b)
{
return a.x==b.x?a.y<b.y:a.x<b.x;
}
bool cmpy(Point a,Point b)
{
return a.y==b.y?a.x<b.x:a.y<b.y;
}
void Dijkstra()
{
memset(d,0x3f,sizeof(d));
for(d[s]=0, q.push(Node(s, 0)); !q.empty(); )
{
Node e = q.top(); q.pop();
int u=e.u;
if(done[u]) continue;
done[u]=1;
for(int i=hd[u];i;i=nex[i])
{
int v=to[i];
if(d[v] > d[u] + val[i])
{
d[v] = d[u] + val[i];
q.push(Node(v, d[v]));
}
}
}
}
int main()
{
int i,j,k;
// setIO("input");
scanf("%d%d",&n,&m);
for(i=2;i<=m+1;++i)
{
scanf("%d%d",&t[i].x,&t[i].y);
id[i][0]=++tot;
id[i][1]=++tot;
t[i].id=i;
}
scanf("%d%d",&t[1].x,&t[1].y);
id[1][0]=++tot;
id[1][1]=++tot;
t[1].id=1;
m+=2;
scanf("%d%d",&t[m].x,&t[m].y);
id[m][0]=++tot;
id[m][1]=++tot;
t[m].id=m;
for(i=1;i<=m;++i)
{
addedge(id[i][0],id[i][1],1);
addedge(id[i][1],id[i][0],1);
}
sort(t+1,t+1+m,cmpx);
for(i=1;i<=m;i=j)
{
for(j=i;j<=m&&t[j].x==t[i].x;++j);
for(k=i+1;k<j;++k)
{
addedge(id[t[k-1].id][1], id[t[k].id][1], 2 * (t[k].y-t[k-1].y));
addedge(id[t[k].id][1], id[t[k-1].id][1], 2 * (t[k].y-t[k-1].y));
}
}
sort(t+1,t+1+m,cmpy);
for(i=1;i<=m;i=j)
{
for(j=i;j<=m&&t[j].y==t[i].y;++j);
for(k=i+1;k<j;++k)
{
addedge(id[t[k-1].id][0], id[t[k].id][0], 2 * (t[k].x-t[k-1].x));
addedge(id[t[k].id][0], id[t[k-1].id][0], 2 * (t[k].x-t[k-1].x));
}
} s=0, T=++tot; addedge(s, id[1][0], 0);
addedge(s, id[1][1], 0); addedge(id[m][0], T, 0);
addedge(id[m][1], T, 0);
Dijkstra();
printf("%d\n",d[T]);
return 0;
}

  

最新文章

  1. ASP.NET实现微信功能(2)(服务号高级群发)
  2. 二十五、JDK1.5新特性---枚举
  3. eclipse rcp 打包出适合不同操作系统和操作位数.
  4. GitHub入门教程 Hello World for GitHub
  5. 禁止apache显示目录索引的常见方法(apache禁止列目录)
  6. SQL错误级别 状态 怎么定义
  7. remot debug
  8. vue.js笔记
  9. 关于ActionBar的向下兼容
  10. python进阶(5):组合,继承
  11. 让所有浏览器支持HTML5 video视频标签
  12. dataframe操作
  13. C++类型检查
  14. 洛谷 P1823 音乐会的等待
  15. [Python 从入门到放弃] 3. BIF(内建函数)
  16. Tensorflow线程和队列
  17. 爬取乌云上所有人民币和乌云符号的漏洞(python脚本)
  18. Android-----代码实现打开手机第三方应用APP
  19. 读jQuery之二十(Deferred对象)--(转)
  20. sql server使用sql插入中文字符串乱码问题

热门文章

  1. LeetCode 答案(python)18-24
  2. MyBatis 源码篇-DataSource
  3. 怎样测试nginx.conf配置文件的正确性
  4. spring-boot-plus CORS跨域处理
  5. ORACLE触发器的自治事务的注意事项
  6. 【原创】编程基础之Jekins
  7. 安卓开发之获取SD卡空间数据
  8. 16.Listener(监听器)
  9. 文件 file open函数的打开及 函数的调用
  10. 微信小程序文章收录