题目描述
传送门
题目大意：给定平面上的n个点，定义(x1,y1)到(x2,y2)的费用为min(|x1-x2|,|y1-y2|)，求从1号点走到n号点的最小费用。
题解
分别按照xy排序，然后相邻点连边，跑最短路就行了 写了一发堆优化dijkstra，竟然把大小记反了！
代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
#define LL long long
#define N 1000005
int n;
struct data{LL x,y;
int id;}p[N];
int tot,point[N],nxt[N],v[N];LL c[N];
LL dis[N];
bool vis[N];
priority_queue < pair<LL,
int> > q;
int cmpx(data a,data b){
return a.x<b.x||(a.x==b.x&&a.y<b.y);}
int cmpy(data a,data b){
return a.y<b.y||(a.y==b.y&&a.x<b.x);}
LL Abs(LL x){
return (x>
0)?x:-x;}
LL calc(data a,data b){
return min(Abs(a.x-b.x),Abs(a.y-b.y));}
void add(
int x,
int y,LL z)
{
++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; c[tot]=-z;
++tot; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; c[tot]=-z;
}
void dijkstra(
int s,
int t)
{
memset(dis,
128,
sizeof(dis));
dis[s]=
0;q.push(make_pair(
0,s));
while (!q.empty())
{
pair<LL,
int> now=q.top();q.pop();
int x=now.second;
if (vis[x])
continue;vis[x]=
1;
for (
int i=point[x];i;i=nxt[i])
if (dis[v[i]]<dis[x]+c[i])
{
dis[v[i]]=dis[x]+c[i];
q.push(make_pair(dis[v[i]],v[i]));
}
}
}
int main()
{
scanf(
"%d",&n);
for (
int i=
1;i<=n;++i)
scanf(
"%lld%lld",&p[i].x,&p[i].y),p[i].id=i;
sort(p+
1,p+n+
1,cmpx);
for (
int i=
1;i<n;++i) add(p[i].id,p[i+
1].id,calc(p[i],p[i+
1]));
sort(p+
1,p+n+
1,cmpy);
for (
int i=
1;i<n;++i) add(p[i].id,p[i+
1].id,calc(p[i],p[i+
1]));
dijkstra(
1,n);
printf(
"%lld\n",-dis[n]);
}
