题意

题面已经较为清楚，翻译有一处翻译错误，第三个操作应为“花费为 $A_{i,j}$。”

做法

本题符合 atcoder 的一贯风格，将三个比较简单的操作和一个较为困难的操作放在一起加以迷惑，需要选手多加思考。

本题解为官方题解做法。

前三个操作可以直接按照题面要求暴力建边解决。接下来考虑第四个操作：

首先考虑如果花费为 $k$ 该如何处理，发现只要转化为对于每个点 $P(i,j)$ 建到点 $(i+1,j)$ 的长度为 $1$ 的边即可。

再考虑花费为 $k+1$，想到一种类似分层图的做法：

把图拆为两层，一层为前三个操作建边所得图，一层为上述做法所建得的图。第一层建立到第二层长度为 $1$ 的边，第二层建立到第一层长度为 $0$ 的边。

具体的，

对于每个点 $P(i,j)(i\)$，建立一个点 $Q(i,j)$ 和如下边：

  • $P(i,j)$ 到点 $Q(i,j)$，长度为1的边。
  • $Q(i,j)$ 到点 $Q(i-1,j)$，长度为1的边。
  • $Q(i,j)$ 到点 $P(i,j)$，长度为0的边。

之后跑 dijkstra 即可通过本题。

代码

该代码较为朴实，较为科技（ NOI 系列竞赛不能使用）的代码请参见官方题解。

#include<bits/stdc++.h>
using namespace std;
vector<int> v[550005],w[550005];
int n,m,a[505][505],b[505][505];
long long dis[550005];
bool vis[550005];
priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int> > > pq;
int td(int tp,int i,int j){//获取节点编号，tp表示在哪一层上。
    if(tp) return 250000+i*500+j;
    else return i*500+j;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m-1;j++) cin>>a[i][j];
    for(int i=1;i<=n-1;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++){
            int nd1=td(0,i,j),nd2=td(1,i,j);
            if(j<m) v[nd1].push_back(td(0,i,j+1)),w[nd1].push_back(a[i][j]);
            if(j>=2) v[nd1].push_back(td(0,i,j-1)),w[nd1].push_back(a[i][j-1]);
            if(i<n) v[nd1].push_back(td(0,i+1,j)),w[nd1].push_back(b[i][j]);
            if(j>=2){//第四个操作
                v[nd1].push_back(nd2);w[nd1].push_back(1);
                v[nd2].push_back(td(1,i-1,j));w[nd2].push_back(1);
                v[nd2].push_back(nd1);w[nd2].push_back(0);
            }
        }
    memset(dis,0x3f,sizeof(dis));
    vis[td(0,1,1)]=1,dis[td(0,1,1)]=0;
    pq.push(make_pair(0,td(0,1,1)));
    while(!pq.empty()){
        pair<int,int> fr=pq.top();pq.pop();
        int nt=fr.second;
        for(int i=0;i<v[nt].size();i++){
            if(dis[v[nt][i]]>dis[nt]+w[nt][i]){
                dis[v[nt][i]]=dis[nt]+w[nt][i];
                if(!vis[v[nt][i]]) pq.push(make_pair(dis[v[nt][i]],v[nt][i]));
            } 
        }
    }
    cout<<dis[td(0,n,m)];
    return 0;
}