题目链接

解题思路

本题难度和CSP-S 2020 T1（弱数据）相近

不难得到一个推论：如果你t时刻出发走某一条路径，被某个洪水挡住了，无论你走其他什么路径，总会被挡住。

然后之后又得到一条推论：如果你在t时刻出发去终点，如果某个洪水在半路上挡住了你，那它必然比你更先到达终点。

所以本题就变成了什么时候会有洪水淹没起点，和什么时候会有洪水淹没终点。

代码

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9+7;
int mint;
int t[105],x[105],y[105];
int main(){
    int n,q;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&t[i],&x[i],&y[i]);
    }
    int a,b,c,d;
    for(int i=1;i<=q;i++){
        mint=inf;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        for(int j=1;j<=n;j++){
            mint=min(mint,t[j]+abs(x[j]-c)+abs(y[j]-d)-abs(a-c)-abs(b-d));
            mint=min(mint,t[j]+abs(x[j]-a)+abs(y[j]-b));
        }
        printf("%d\n",mint-1);
    }
    return 0;
} 

本文链接：http://kaispace.com.cn/index.php/archives/792/

如果未注明出处，复制公开后需将注明本博客链接。
打赏作者