论我在模拟赛时信誓旦旦的说做这道题最有前途并用长达 $116$ 行的代码华丽的骗了高达 $5$ 分。

这题显然是不能暴力建边跑最短路的。

我们要考虑怎么更新起点到任意一点的最短距离

对于红色起点 $(s_x,s_y)$ 考虑向外更新最短路，如果是红色菱形内部（可直接到达）的点，一定是直接走到最优

那么对于没法直接到达的黑色点 $(e_x,e_y)$ ,设菱形内部某点 $(k_x,k_y)$ 且该点可以到达 $(e_x,e_y)$ , $dis[e_x][e_y]$ 可能由任意一个 $dis[k_x][k_y]+a[i][j]$ 更新，但是如果每个 $k$ 点都枚举一遍还会会被卡时间

但是我们能发现一个性质，如果 $a[k_x][k_y]$ 最小(绿色边)，那我们可以只更新这一次，因为不会再有其它更优松弛（也就是不考虑黑色边因为不优），也就是说只需要在确保该次更新是最优的后给 $e$ 点打标记，从此不在更新

如何确保更新是最优的： 在优先队列中传入 $dis[i][j]+a[i][j]$,如图，因为红到绿到黑是最优更新，所以按照红跳到绿的代价加上绿往任意点跳的代价排序

如何打标记： 可以对每一行建一个并查集，每次查找这一行第一个没被更新且可以到达的点更新，并把指针后移，可以参考这篇文章

代码如下

#include<bits/stdc++.h>
using namespace std;
const long long INF=1e15+17;
int top[160][160];//并查集
int n,m,res,da,x[5],y[5],a[160][160],b[160][160];
long long dis[160][160],ans[10];
int findF(int top[],int x){//并查集 
	return top[x]==x ? x:(top[x]=findF(top,top[x]));
}
struct node{
	long long dis;
	int x,y; 
};
bool operator <(node A,node B){//还是不喜欢重载运算符但是也没办法了 
	return A.dis>B.dis; 
}
void dij(int k){
	node X;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m+1;j++){
			dis[i][j]=INF;
			top[i][j]=j;//初始化第i行的并查集 
		}
	}
	priority_queue<node> qi;
	qi.push((node){ a[x[k]][y[k]] , x[k] , y[k]});//起点入堆
	top[x[k]][y[k]]=y[k]+1;//并查集指针右移
	dis[x[k]][y[k]]=0;
	while(!qi.empty()){
		X=qi.top();
		qi.pop();
		int len=b[X.x][X.y],len2;
		int xx=max(1,X.x-len);
		int yy=min(n,X.x+len); //横向距离边界 
		for(int i=xx;i<=yy;i++){
			len2=len-abs(X.x-i);
			int ll=max(1,X.y-len2);
			int rr=min(m,X.y+len2);//纵向距离边界
			for(int j=findF(top[i],ll);j<=rr;j=findF(top[i],j)){//并查集跳点优化染色
				qi.push((node){X.dis+a[i][j],i,j});
				dis[i][j]=X.dis; 
				top[i][j]=j+1;
				if(dis[x[1]][y[1]]!=INF&&dis[x[2]][y[2]]!=INF&&dis[x[3]][y[3]]!=INF){//剪枝 
					return;
				}
			} 
		}
	}
}
int main(){
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin >> b[i][j];
		}
	} 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin >> a[i][j];
		}
	} 
	for(int i=1;i<=3;i++) cin >> x[i] >> y[i];
	for(int i=1;i<=3;i++){
		dij(i);
		for(int j=1;j<=3;j++){
			ans[j]+=dis[x[j]][y[j]];
		}
	}
	long long min_ans = min(min(ans[1],ans[2]),ans[3]);
	if(min_ans>=INF){
		cout << "Impossible";
		return 0;
	} 
    if (ans[1] == min_ans) {
        cout << "Alice\n" << min_ans;
    } else if (ans[2] == min_ans) {
        cout << "Bessie\n" << min_ans;
    } else {
        cout << "Carrie\n" << min_ans;
    }
	return 0;
}

抽象。这个题非常的有趣。

我们注意到一个点最多被更新一次，然后我们就可以考虑用链表删除掉没用的点。

然后就没有然后了。

#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;
}