题解 P4730 【孤舟蓑笠翁】

· · 题解

《江雪》系列第三题

这道题可以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;
}