P4473 题解

#include<bits/stdc++.h>
using namespace std;
int D[205][205];
long long C[205][205],xa,ya,xb,yb,xc,yc;
long long stp[3][205][205];
int pre[3][205][205],nxt[3][205][205];
bool del[3][205][205];int n,m;
inline void doit(int op,int sx,int sy){
	priority_queue<pair<long long,int> >pq;
	memset(stp[op],0x3f,sizeof stp[op]);
	memset(del[op],0,sizeof del[op]);
	stp[op][sx][sy]=0;
	del[op][sx][sy]=1;
	for(int i=1; i<=n; i++){
		nxt[op][i][0]=1;
		for(int j=1; j<=m; j++)pre[op][i][j]=j-1,nxt[op][i][j]=j+1;
	}
	pre[op][sx][nxt[op][sx][sy]]=pre[op][sx][sy];
	nxt[op][sx][pre[op][sx][sy]]=nxt[op][sx][sy];
	pq.push(make_pair(-C[sx][sy],sx*(m+1)+sy));
	while(pq.size()){
		int x=pq.top().second;pq.pop(); 
		int y=x%(m+1);x/=(m+1);
//		cout<<stp[op][x][y]<<" "<<x<<" "<<y<<endl;
		long long dist=-pq.top().first;
		for(int i=max(1,x-D[x][y]); i<=min(n,x+D[x][y]); i++){
			int j=nxt[op][i][0];
			while(j!=m+1&&j<=min(m,y+D[x][y]-abs(x-i))){
				if(j<max(1,y-D[x][y]+abs(x-i))||del[op][i][j]){
					j=nxt[op][i][j];
					continue;
				}
				stp[op][i][j]=stp[op][x][y]+C[x][y];
				del[op][i][j]=1;
				pre[op][i][nxt[op][i][j]]=pre[op][i][j];
				nxt[op][i][pre[op][i][j]]=nxt[op][i][j];
				pq.push(make_pair(-stp[op][i][j]-C[i][j],i*(m+1)+j));
				j=nxt[op][i][j];
			}
		}
	}return;
}
string ans[4]={"","Alice","Bessie","Carrie"};
//这个地方是我们教练魔改过题面，我就懒得改了
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			scanf("%d",&D[i][j]),D[i][j]=min(D[i][j],300);
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			scanf("%lld",&C[i][j]);	
	scanf("%d%d%d%d%d%d",&xa,&ya,&xb,&yb,&xc,&yc);
	doit(0,xa,ya),doit(1,xb,yb),doit(2,xc,yc);
	long long res1=stp[1][xa][ya]+stp[2][xa][ya],res2=stp[0][xb][yb]+stp[2][xb][yb],res3=stp[1][xc][yc]+stp[0][xc][yc];
	int id=1;
//	cout<<res1<<" "<<res2<<" "<<res3<<endl;
	if(res1>res2)res1=res2,id=2;
	if(res1>res3)res1=res3,id=3;
	if(res1>150000000000)printf("Impossible");
	else cout<<ans[id]<<endl<<res1;
	return 0;
}