P6797 「StOI-2」不朽的逃亡者

_•́へ•́╬_ · 2022-11-06 19:02:47 · 题解

和std不同。剪枝后的分层图最短路。

思路

点 (o,i,j) 表示已经拿了 o 个人，现在我位置在 (i,j)，还没计算 (i,j) 位置的危险值，已经走过的路上的危险值之和。

酱紫转移：

• 不吃 d_{ij}，找一个包含 (i,j) 的矩形 [ax,bx,ay,by]，即满足 ax\leq i\leq bx,ay\leq j\leq by，然后转移到 (bx+1,k) | j\leq k\leq by 和 (k,by+1) | i\leq k\leq bx。
• 吃了 d_{ij}，转移到 (i+1,j) 和 (i,j+1)。

剪枝

先来一个卡常小玩意：按 o 从小到大进行转移，当前 o 维护堆，o+1 维护一个 vector，++o 时再用 vector 构建堆。

最关键的剪枝来喽：

根据 dij 的特殊性质，同一个 o 的危险值是不降的。而通过矩形转移的时候不吃 d，也就是说在 o 优的到 o+1 也优。这是剪枝可行的前提。

那么对于每个矩形，记录一下已经更新过的 (bx+1,k) 和 (k,by+1)，后面遇到更劣的时候就不更新了。我的做法是记了两个 k 更新到的最小位置值。

复杂度分析

有 nm(w+1) 个点。

有至多 (n+m)k(w+1) 条边。

算上堆，复杂度 \mathcal O(nmw+(n+m)kw\log(n+m)k)。

code

#include<stdio.h>
#include<queue>
#include<string.h>
#define N 201
#define M 101
using namespace std;
inline char nc()
{
    static char buf[99999],*l,*r;
    return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
    char c=nc();for(;c<'0'||'9'<c;c=nc());
    for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
struct node
{
    int i,j;long long ans;
    inline node(){}
    inline node(const int&a,const int&b,const long long&c)
        {i=a;j=b;ans=c;}
    inline bool operator<(const node&kkk)const{return ans>kkk.ans;}
};
int n,m,p,w,ax[N],bx[N],ay[N],by[N],ux[M][N],uy[M][N],a[N][N];
priority_queue<node>q;vector<node>qwq[M];
long long minn=1ll<<60,ans[M][N][N];
main()
{
    read(n);read(m);read(p);read(w);if(w>p)w=p;
    for(int i=0;i<n;++i)for(int j=0;j<m;read(a[i][j++]));
    for(int i=0;i<p;++i)
    {
        read(ax[i]);read(bx[i]);read(ay[i]);read(by[i]);
        --ax[i];--bx[i];--ay[i];--by[i];
        for(int j=0;j<=w;++j)ux[j][i]=bx[i],uy[j][i]=by[i];
    }
    memset(ans,0x3f,sizeof(ans));
    ans[0][0][0]=0;qwq[0].emplace_back(0,0,0);
    for(int o=0;o<=w;++o)
    {
        q=priority_queue<node>(qwq[o].begin(),qwq[o].end());
        for(node i;q.size();)
        {
            i=q.top();q.pop();
            if(minn<=i.ans)break;
            if(i.i+i.j>=n+m-1){minn=i.ans;break;}
            if(i.i==n||i.j==m)continue;
            if(o<w)for(int j=0;j<p;++j)if(ax[j]<=i.i&&i.i<=bx[j])
                if(ay[j]<=i.j&&i.j<=by[j])
            {
                for(int k=i.i;k<=ux[o][j];++k)
                    if(ans[o+1][k][by[j]+1]>i.ans)
                        qwq[o+1].emplace_back(k,by[j]+1,
                            ans[o+1][k][by[j]+1]=i.ans);
                if(i.i<=ux[o][j])ux[o][j]=i.i-1;
                for(int k=i.j;k<=uy[o][j];++k)
                    if(ans[o+1][bx[j]+1][k]>i.ans)
                        qwq[o+1].emplace_back(bx[j]+1,k,
                            ans[o+1][bx[j]+1][k]=i.ans);
                if(i.j<=uy[o][j])uy[o][j]=i.j-1;
            }
            i.ans+=a[i.i][i.j];
            if(ans[o][i.i+1][i.j]>i.ans)
                q.emplace(i.i+1,i.j,ans[o][i.i+1][i.j]=i.ans);
            if(ans[o][i.i][i.j+1]>i.ans)
                q.emplace(i.i,i.j+1,ans[o][i.i][i.j+1]=i.ans);
        }
    }
    printf("%lld",minn);
}