358G AtCoder Tour

358G

思维题

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,s,t,vis[55][55][2505],k;
ll dis[55][55][2505],v[55][55],ans;
int mvx[] = {-1,1,0,0};
int mvy[] = {0,0,-1,1};
struct Node{
    int x,y,d;
};
queue<Node> q;
void spfa(){
    while(!q.empty()){
        Node t = q.front(); q.pop();
        for(int i = 0; i < 4; i++){
            int nx = t.x + mvx[i];
            int ny = t.y + mvy[i];
            int nd = t.d + 1;
            if(nx < 1 || ny < 1 || nx > n || ny > m || nd > min(k,2500)) continue;
            // cout<<"n: "<<nx<<" "<<ny<<" "<<nd<<endl;
            if(dis[t.x][t.y][t.d] + v[nx][ny] > dis[nx][ny][nd]){
                dis[nx][ny][nd] = dis[t.x][t.y][t.d] + v[nx][ny];
                if(vis[nx][ny][nd] == 0){
                    vis[nx][ny][nd] = 1;
                    q.push((Node){nx, ny, nd});
                }
            } 
        }
    }
}
int main(){
    cin>>n>>m>>k>>s>>t;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin>>v[i][j];
        }
    }
    memset(dis, 0xcf, sizeof dis);
    q.push((Node){s,t,0});
    vis[s][t][0] = 1;
    dis[s][t][0] = 0;
    spfa();
    // cout<<dis[2][3][4]<<endl;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            for(int p = 0; p <= min(2500, k); p++)//一开始写的k<=1
                ans = max(ans, dis[i][j][p] + (k-p)*v[i][j]);
        }
    }
    cout<<ans<<endl;
    return 0;
}