循环队列基础知识
1.循环队列需要几个参数来确定
循环队列需要2个参数，front和rear
2.循环队列各个参数的含义
（1）队列初始化时，front和rear值都为零；
（2）当队列不为空时，front指向队列的第一个元素，rear指向队列最后一个元素的下一个位置；
（3）当队列为空时，front与rear的值相等，但不一定为零；
3.循环队列入队的伪算法
（1）把值存在rear所在的位置；
（2）rear=（rear+1）%maxsize ，其中maxsize代表数组的长度；
4.循环队列出队的伪算法
（1）先保存出队的值；
（2）front=（front+1）%maxsize ，其中maxsize代表数组的长度；
5.如何判断循环队列是否为空
if（front==rear）
队列空；
else
队列不空；
6.如何判断循环队列是否为满？
这个问题比较复杂，假设数组的存数空间为7，此时已经存放1，a，5,7,22,90六个元素了，如果在往数组中添加一个元素，则rear=front；此时，队列满与队列空的判断条件front=rear相同，这样的话我们就不能判断队列到底是空还是满了；
解决这个问题有两个办法：一是增加一个参数，用来记录数组中当前元素的个数；第二个办法是，少用一个存储空间，也就是数组的最后一个存数空间不用，当（rear+1）%maxsiz=front时，队列满；
例题：
4152: [AMPPZ2014]The Captain
Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 664 Solved: 256
[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
首先，我们可以无视min，直接两点之间建一条|x2-x1|的边和一条|y2-y1|的边
可以发现，对于点(x1,y1),(x2,y2),(x3,y3)，x1<x2<x3，则|x2-x1|+|x3-x2| = |x3-x1|
所以从x1连向x3用x坐标计算权值的边是没有用的。
Y同理
所以每个点只需要向上下左右最靠近的点连边，排序即可
先按x排序, 然后只有相邻节点的边才有用, 我们连起来, 再按y排序做相同操作...然后就跑dijikstra，这个题目是卡spfa的。
而且dijistra不用队优化会超时的。呵呵~。
#include<cstring>
#define N 200010
#define inf (unsigned long long)((1<<63)-1)/*直接复制（1<<63）-1是会出现-1的，在前面要有ull*/
#include<iostream>
using namespace std;
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<algorithm>
struct Edge{
int v,last;
unsigned long long w;
}edge[N<<];
struct Jg{
int x,y;
}dian[N];
int head[N],X[N],Y[N],n,t=;
unsigned long long dis[N];
struct Dis{
int id;
unsigned long long d;
Dis(){d=inf;}
bool operator <(Dis K)
const{return d>K.d; }/*优先队列是默认大的元素在前，这个重载运算符只能对<，把他变成>即可*/
};
priority_queue<Dis>Q;
bool vis[N]={false};
inline int read()
{
int ret=,ff=;
char s=getchar();
while(s<''||s>'')
{
if(s=='-') ff=-;
s=getchar();
}
while(s>=''&&s<='')
{
ret=ret*+s-'';
s=getchar();
}
return ret*ff;
}
void input()
{
n=read();
for(int i=;i<=n;++i)
{
dian[i].x=read();dian[i].y=read();
X[i]=Y[i]=i;
}
}
bool cmpx(int a,int b)/*排序，a，b代表X[N]数组中的某两个元素，他们代表的是dian数组的编号*/
{
return dian[a].x<dian[b].x;
}
bool cmpy(int a,int b)
{
return dian[a].y<dian[b].y;
}
void add_edge(int a,int b,int falgg)
{
if(falgg==)
{
++t;
edge[t].v=b;
edge[t].w=abs(dian[a].x-dian[b].x);
edge[t].last=head[a];
head[a]=t;
}
else
{
++t;
edge[t].v=b;
edge[t].w=abs(dian[a].y-dian[b].y);
edge[t].last=head[a];
head[a]=t;
}
}
void build_line()
{/*先按x排序, 然后只有相邻节点的边才有用, 我们连起来, 再按y排序做相同操作.*/
sort(X+,X+n+,cmpx);
for(int i=;i<=n;++i)
{
add_edge(X[i],X[i-],);
add_edge(X[i-],X[i],);
}
sort(Y+,Y+n+,cmpy);
for(int i=;i<=n;++i)
{
add_edge(Y[i],Y[i-],);
add_edge(Y[i-],Y[i],);
}
}
void dijkstra()
{
for(int i=;i<=n;++i)
dis[i]=inf;
dis[]=;
Dis now;
now.id=;now.d=;
Q.push(now);
while(!Q.empty())
{
Dis nowe=Q.top();
Q.pop();
if(dis[nowe.id]!=nowe.d)continue;
if(vis[nowe.id])continue;
vis[nowe.id]=true;
for(int l=head[nowe.id];l;l=edge[l].last)
{
if(!vis[edge[l].v]&&dis[edge[l].v]>dis[nowe.id]+edge[l].w)
{
dis[edge[l].v]=dis[nowe.id]+edge[l].w;
Dis now;
now.id=edge[l].v;now.d=dis[edge[l].v];
Q.push(now);
}
}
}
}
int main()
{
input();
build_line();
dijkstra();
cout<<dis[n];
return ;
}