BZOJ 4152: [AMPPZ2014]The Captain(最短路)
程序员文章站
2022-03-25 22:52:58
Description 给定平面上的n个点,定义(x1,y1)到(x2,y2)的费用为min(|x1-x2|,|y1-y2|),求从1号点走到n号点的最小费用。 给定平面上的n个点,定义(x1,y1)到(x2,y2)的费用为min(|x1-x2|,|y1-y2|),求从1号点走到n号点的最小费用。 ......
Submit: 1550 Solved: 619
[Submit][Status][Discuss]
Description
给定平面上的n个点,定义(x1,y1)到(x2,y2)的费用为min(|x1-x2|,|y1-y2|),求从1号点走到n号点的最小费用。
Input
第一行包含一个正整数n(2<=n<=200000),表示点数。
接下来n行,每行包含两个整数x[i],y[i](0<=x[i],y[i]<=10^9),依次表示每个点的坐标。
Output
一个整数,即最小费用。
Sample Input
5
2 2
1 1
4 5
7 1
6 7
2 2
1 1
4 5
7 1
6 7
Sample Output
2
HINT
Source
很有意思的一道题目
两个点之间的费用为min(|x1-x2|,|y1-y2|),就相当于对于x和y分别连边。
对于1,2,3这三个点,若x1<=x2<=x3,不难发现|x1-x3|这条边没有必要连。
那么我们把所有点按x排序,每个点向相邻点连权值为x差的绝对值的边。
再把所有点按y排序,同理。
然后直接跑最短路即可。
记得开long long
#include<cstdio> #include<algorithm> #include<queue> #include<cstring> #define Pair pair<int,int> #define F first #define S second #define int long long const int MAXN=1e6+10; using namespace std; inline int read() { char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int N; struct node { int id,x,y; }Point[MAXN]; int comp(const node &a,const node &b){return a.x<b.x;} int comp2(const node &a,const node &b){return a.y<b.y;} int dis[MAXN],vis[MAXN]; struct E { int u,v,w,nxt; }edge[MAXN]; int head[MAXN],num=1; inline void AddEdge(int x,int y,int z) { edge[num].u=x;edge[num].v=y;edge[num].w=z;edge[num].nxt=head[x]; head[x]=num++; } void Dijstra() { memset(dis,0xf,sizeof(dis));dis[1]=0; priority_queue<Pair>q; q.push(make_pair(0,1)); while(q.size()!=0) { while(vis[q.top().S]&&q.size()>0) q.pop(); Pair p=q.top(); vis[p.S]=1; for(int i=head[p.S];i!=-1;i=edge[i].nxt) if(dis[edge[i].v]>dis[p.S]+edge[i].w) dis[edge[i].v]=dis[p.S]+edge[i].w, q.push(make_pair(-dis[edge[i].v],edge[i].v)); } printf("%lld",dis[N]); } main() { #ifdef WIN32 freopen("a.in","r",stdin); #else #endif memset(head,-1,sizeof(head)); N=read(); for(int i=1;i<=N;i++) Point[i].id=i,Point[i].x=read(),Point[i].y=read(); sort(Point+1,Point+N+1,comp); for(int i=1;i<=N-1;i++) AddEdge(Point[i].id,Point[i+1].id,Point[i+1].x-Point[i].x), AddEdge(Point[i+1].id,Point[i].id,Point[i+1].x-Point[i].x); sort(Point+1,Point+N+1,comp2); for(int i=1;i<=N-1;i++) AddEdge(Point[i].id,Point[i+1].id,Point[i+1].y-Point[i].y), AddEdge(Point[i+1].id,Point[i].id,Point[i+1].y-Point[i].y); Dijstra(); return 0; }
上一篇: 正则表达式
下一篇: C++ 输入、输出运算符重载