不正经题解 - 广搜或曼哈顿距离

一种容易想到的方法是广搜。从最早的军团开始搜，到第二个军团的时间了就把第二个军团也加进来一起搜，以此类推。这种做法的时空复杂度都是 $O(n^2)$ 的，常数还很大，需要有一定的卡常经验才打得好，可惜时限 5s 几乎卡不掉多少。

一种不容易想到的方法是带权曼哈顿距离。我们只需要暴力枚举敌方，计算每一个敌方最早被消灭的时刻。容易发现，被消灭的时刻就是军团到这个敌方的曼哈顿距离+军团到达战场的时间的最小值。所以我们只需要再枚举一下军团就行了。时间复杂度还是 $O(n^2)$，空间复杂度变为了 $O(n)$。然而实际跑起来比广搜快得多，一是因为常数极小 ，二是因为数据过水。

做法一代码如下。

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

#define PRI(x) printf(#x" : %d\n",x)

bool vis[5005][5005];
bool tag[5005][5005];
int dx[]={0,-1,0,1},
    dy[]={-1,0,1,0};
int n,m,k;
struct event{
	int x,y,t;
}e[5005];

inline int read(){
    register int x=0;register char ch=getchar();
    while(ch<'0'||ch>'9'){ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x;
}

inline bool cmp(event& x,event& y){
	return x.t<y.t;
}
inline bool check(int& x,int& y){
	return x>0&&x<=n&&y>0&&y<=n&&!vis[x][y];
}

int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(register int i=1;i<=m;i++){
		tag[read()][read()]=1;
	}
	for(register int i=1;i<=k;i++){
		e[i].x=read(),e[i].y=read(),e[i].t=read();
	}
	
	sort(e+1,e+1+k,cmp);
	register int nowi,cnt=2;
	queue<event>q;
	q.push(e[1]);
	vis[e[1].x][e[1].y]=1;
	while(m){
		event f=q.front();
		q.pop();
		if(tag[f.x][f.y]){
			tag[f.x][f.y]=0;
			m--;
		}
		nowi=f.t;
		if(f.t==e[cnt].t){
			while(cnt<=k&&e[cnt].t==f.t) q.push(e[cnt++]);
		}
		for(register int i=0;i<=3;i++){
			int nx=f.x+dx[i],ny=f.y+dy[i];
			if(check(nx,ny)){
				vis[nx][ny]=1;
				q.push({nx,ny,f.t+1});
			}
		}
	}
	printf("%d",nowi);
	
	return 0;
}

做法二代码如下。

#include <cstdio>
#include <algorithm>
#include <memory.h>
using namespace std;

#define pri(x) printf(#x":%d\n",x);

inline int read(){
    register int x=0;register char ch=getchar();
    while(ch<'0'||ch>'9'){ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x;
}

struct pos1{
	int x,y;
}a[5005];

struct pos2{
	int x,y,t;
}b[5005];

int main(){
	int n,m,k;
	scanf("%d%d%d",&n,&m,&k);
	for(register int i=1;i<=m;i++)
		a[i]={read(),read()};
	
	for(register int i=1;i<=k;i++)
		b[i]={read(),read(),read()};
	
	int ans=0;
	for(register int i=1;i<=m;i++){
		int time=200000000;
		for(register int j=1;j<=k;j++)
			time=min(time,abs(a[i].x-b[j].x)+abs(a[i].y-b[j].y)+b[j].t);
		ans=max(ans,time);
	}
	printf("%d\n",ans);
	
	return 0;
}