CF1869B 2D Traveling

One_JuRuo · 2023-09-11 08:31:55 · 题解

思路

首先思考，除了 a 和 b 我们不应该到达任何非主要城市。

理由很简单，两点之间线段最短，如果我们目前要从 u 前往 v 且 u 和 v 不都是主要城市，即 u 到 v 需要花钱，那么如果再选择一个不是主要城市的 k，那么就要增加若干的花费。当然，增加的花费可能为 0，但是我们完全没必要多转几次，因为这无法让答案变得更优。

但是主要城市之间可以随便转乘，因为都不增加花费，那么就有两种方式：

• 直接从 a 到 b。

• 从 a 到离它最近的主要城市，途中转移几次到离 b 最近的主要城市，再到 b。

如果令 dis(i,j) 表示从 i 到 j 的花费，fa 表示离 a 最近的主要城市，fb 表示离 b 最近的主要城市，那么答案就是 \min(dis(a,b),dis(a,fa)+dis(fa,fb)+dis(fb,b))。

首先 dis(i,j) 可以直接计算得出，所以不需要考虑，又因为 dis(fa,fb)=0 所以也不需要考虑，我们只需要提前预处理出 fa 和 fb，或者预处理 dis(a,fa) 和 dis(b,fb) 即可。

AC code

#include<bits/stdc++.h>
using namespace std;
long long T,n,k,a,b,x[200005],y[200005],ans1,ans2;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld%lld%lld%lld",&n,&k,&a,&b),ans1=ans2=0x3f3f3f3f3f3f3f3f;
        for(long long i=1;i<=n;++i) scanf("%lld%lld",&x[i],&y[i]);
        if(a<=k) ans1=0;//注意特判a、b本身就是主要城市的情况
        else for(long long i=1;i<=k;++i) ans1=min(ans1,abs(x[i]-x[a])+abs(y[i]-y[a]));
        if(b<=k) ans2=0;
        else for(long long i=1;i<=k;++i) ans2=min(ans2,abs(x[i]-x[b])+abs(y[i]-y[b]));
        printf("%lld\n",min(ans1+ans2,abs(x[a]-x[b])+abs(y[a]-y[b])));
    }
    return 0;
}