一点小细节
查看原帖
一点小细节
575224
_ACACACAC_楼主2022/10/21 22:20

虽然SPFA与迪杰斯特拉的三维数组写法可以过,但是我感觉部分题解还是没注意到一个细节,那就是我们每次暴力枚举汇合点的时候还是最好在统计答案的时候分两种情况来考虑,一种是国王单独走到汇合点加上全部骑士没带国王的情况。一种自然是带上国王的情况。取这两个的最小值即可

之所以我有这种顾虑是因为如果只统计带上国王的情况时,函数返回值会出现inf的情况(测试点1,这种情况设置为死循环),也就是会有带上国王反而不优的情况。但多数题解没有考虑到,数据这方面很难构造,故没有卡掉,但还是需要留意的

  ll minn=1e9;
    ll sum=0;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(qishi[i][j])
            {
                sum+=dis[i][j][0];

                minn=min(minn,dis[i][j][1]-dis[i][j][0]);
            }
        }
    }

    return min(sum+max(abs(kx-x),abs(ky-y)),sum+minn);
2022/10/21 22:20
加载中...