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