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