自动搬运

查看原文

来自洛谷，原作者为

	chaojidouding **

搬运于2025-08-24 22:03:03，当前版本为作者最后更新于2018-12-19 15:27:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

《江雪》系列第三题

这道题可以bfs做

你建立一个新图，先把每一对可停顿点(Pa,Pb)当做新图一个点，然后把dis(Pa,Pb)>Dmax和dis(Pa,Pb)<Dmin的点判掉，再把可抵达的点连边，这样题目就转化成了一个新问题：给你一个无向图，边权是1，给你一些关键点，让你求距离每一个关键点最短的关键点。

然后我们把所有的关键点push进队列里bfs，可以求出离每个点最近的关键点距离dis，然后我们可以枚举每一条边,设他两端点是x,y然后我们就分别更新距离x，y最近的关键点，把这个点的答案和dis[x]+dis[y]取最小值就可以了。

代码：

#include<cstdio>
#include<iostream>
#include<vector>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int q[1010101],viss[1010101],dis[1010101],ans[1010101],x[10101],y[10101],a[10101],b[10101],type[10101],vis[1010101],u[1010101],v[1010101];
vector<int>s[1010101];
int n,k;
void jiantu(int x,int y)
{
	if(!vis[x]||!vis[y])
		return;
	s[x].push_back(y);
	s[y].push_back(x);
}
int get_dis(int a,int b)
{
	return abs(x[a]-x[b])+abs(y[a]-y[b]);
}
int calc(int x,int y)
{
	return (x-1)*n+y;
}
void bfs()
{
	int t,i,c,y,h,x;
	h=0,t=0;
	for(i=1;i<=k;i++)
		q[t++]=calc(u[i],v[i]),viss[calc(u[i],v[i])]=i,dis[calc(u[i],v[i])]=0;
	while(h<t)
	{
		x=q[h++];
		c=s[x].size();
		for(i=0;i<c;i++)
		{
			y=s[x][i];
			if(viss[y])
				continue;
			dis[y]=dis[x]+1;
			viss[y]=viss[x];
			q[t++]=y;
		}
	}
}
int main()
{
	int m,mx,mn,di,i,j,kk,xx,yy;
	scanf("%d%d",&n,&m);
	scanf("%d%d",&mn,&mx);
	for(i=1;i<=n;i++)
		scanf("%d%d",&x[i],&y[i]);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			di=get_dis(i,j);
			if(di<mn||di>mx)
				continue;
			vis[calc(i,j)]=1;
		}
	}
	scanf("%d",&k);
	for(i=1;i<=k;i++)
		scanf("%d%d",&u[i],&v[i]),ans[i]=1000000007;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&a[i],&b[i],&type[i]);
		if(type[i]==0)
		{
			for(j=1;j<=n;j++)
				jiantu(calc(a[i],j),calc(b[i],j));
		}
		else
		{
			for(j=1;j<=n;j++)
				jiantu(calc(j,a[i]),calc(j,b[i]));
		}
	}
	for(i=1;i<=m;i++)
	{
		for(j=1;j<=m;j++)
		{
			if(type[i]==0&&type[j]==1)
			{
				jiantu(calc(a[i],a[j]),calc(b[i],b[j]));
				jiantu(calc(a[i],b[j]),calc(b[i],a[j]));
			}
		}
	}
	
	bfs();
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
			xx=calc(i,j);
			for(kk=0;kk<s[xx].size();kk++)
			{
				yy=s[xx][kk];
				if(viss[xx]!=viss[yy])
				{
					ans[viss[xx]]=min(ans[viss[xx]],dis[xx]+dis[yy]+1);
					ans[viss[yy]]=min(ans[viss[yy]],dis[xx]+dis[yy]+1);
				}
			}
		}
	for(i=1;i<=k;i++)
	{
		if(ans[i]==1000000007)
			ans[i]=-1;
		printf("%d\n",ans[i]);
	}
	return 0;
}