问题标题: 酷町堂：1632

#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<iomanip>
#include<list>
#include<stack>
using namespace std;
struct node{
    long long ax,ay,v;
};
long long n,m,k,t,a[5005][5005],maxn;
queue<node> q;
void bfs(){
    long long cnt=1;
    node st;
    for(int i=1;i<=m;i++){
        st.ax=1,st.ay=i,st.v=a[1][i];
        maxn=max(maxn,st.v);
        q.push(st);
    }
    while(!q.empty()){
        if(q.front().ax>n){
            break;
        }
        if(q.front().ax!=cnt){
            cnt++;
            for(int i=max((long long)1,q.front().ay-t);i<=min(m,q.front().ay+t);i++){
                if(q.front().ay==i) continue;
                node s;
                s.ax=cnt;
                s.ay=i;
                s.v=q.front().v+a[s.ax][s.ay];
                maxn=max(maxn,s.v);
                q.push(s);
            }
            q.pop();
        }
        else{
            if(q.front().ay+t>m){
                q.pop();
                continue;
            }
            node st;
            st.ax=cnt;
            st.ay=q.front().ay+k;
            st.v=q.front().v+a[st.ax][st.ay];
            maxn=max(maxn,st.v);
            q.push(st);
            q.pop();
        }
    }
}
int main(){
    cin>>n>>m>>k>>t;
    for(int i=1;i<=k;i++){
        int u,v,z;
        cin>>u>>v>>z;
        a[u][v]=z;
    }
    bfs();
    cout<<maxn;
    return 0;
}

@董子墨 @包涵宇

黄子澄在2020-12-04 18:42:52追加了内容

• #include<iostream>
  #include<string>
  #include<cstring>
  #include<cstdio>
  #include<algorithm>
  #include<cmath>
  #include<cstdlib>
  #include<queue>
  #include<iomanip>
  #include<list>
  #include<stack>
  using namespace std;
  struct node{
      long long ax,ay,v;
  };
  long long n,m,k,t,a[5005][5005],maxn;
  queue<node> q;
  void bfs(){
      long long cnt=1;
      node st;
      for(int i=1;i<=m;i++){
          st.ax=1,st.ay=i,st.v=a[1][i];
          maxn=max(maxn,st.v);
          q.push(st);
      }
      while(!q.empty()){
          if(q.front().ax>n){
              break;
          }
          if(q.front().ax==cnt){
              cnt++;
              for(int i=max((long long)1,q.front().ay-t);i<=min(m,q.front().ay+t);i++){
                  node s;
                  s.ax=cnt;
                  s.ay=i;
                  s.v=q.front().v+a[s.ax][s.ay];
                  maxn=max(maxn,s.v);
                  q.push(s);
              }
              q.pop();
          }
          else{
              if(q.front().ay+t>m){
                  q.pop();
                  continue;
              }
              node st;
              st.ax=cnt;
              st.ay=q.front().ay+t;
              st.v=q.front().v+a[st.ax][st.ay];
              maxn=max(maxn,st.v);
              q.push(st);
              q.pop();
          }
      }
  }
  int main(){
      cin>>n>>m>>k>>t;
      for(int i=1;i<=k;i++){
          int u,v,z;
          cin>>u>>v>>z;
          a[u][v]=z;
      }
      bfs();
      cout<<maxn;
      return 0;
  }