bzoj5049 [Lydsy2017年5月月赛]导航系统

本文主要是介绍bzoj5049 [Lydsy2017年5月月赛]导航系统，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

双向广搜+恶毒卡常。

之前没写过双向广搜，昨天打比赛时yy了一下，然后就是惨烈的

这里写图片描述

今天把邻接表改成vector就A了。。。

这里写图片描述

CODE：（白写了register和unsigned int）

#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
#define rg register
#define ui unsigned int
#define N 100005
vector<ui> point[N];
ui dis1[N],dis2[N],h1,t1,h2,t2;
ui q1[N],q2[N];
ui num;
inline ui read()
{rg ui n=0;rg char c=getchar();while(c<'0'||c>'9') c=getchar();while(c>='0'&&c<='9') n=(n<<3)+(n<<1)+c-48,c=getchar();return n;
}
inline int bfs(ui x,ui y)
{q1[++t1]=x,q2[++t2]=y;dis1[x]=dis2[y]=0;while(h1<=t1||h2<=t2){rg bool first=0;if(h2>t2||(h1<=t1&&t1-h1<t2-h2)) first=1;if(first){rg ui end=t1;while(h1<=end){rg ui tmp=q1[h1++],top=point[tmp].size();for(rg ui i=0;i<top;i++){rg ui to=point[tmp][i];if(dis1[to]>dis1[tmp]+1){if(dis2[to]<1e9) return dis1[tmp]+1+dis2[to];dis1[to]=dis1[tmp]+1;q1[++t1]=to;}}}}else{rg ui end=t2;while(h2<=end){rg ui tmp=q2[h2++],top=point[tmp].size();for(rg ui i=0;i<top;i++){rg ui to=point[tmp][i];if(dis2[to]>dis2[tmp]+1){if(dis1[to]<1e9) return dis2[tmp]+1+dis1[to];dis2[to]=dis2[tmp]+1;q2[++t2]=to;}}}}}return -1;
}
int main()
{rg ui n=read(),m=read(),k=read();for(rg ui i=1;i<=m;i++){rg ui x=read(),y=read();point[x].push_back(y);point[y].push_back(x);}while(k--){for(rg ui i=1;i<=n;i++)dis1[i]=dis2[i]=0x3f3f3f3f;h1=h2=1,t1=t2=0;printf("%d\n",bfs(read(),read()));}return 0;
}