我指出了最核心的矛盾点：如果这段代码的时间复杂度真的是 $O(Tnm^2)$，怎么可能通过 T4 $n,m\le10^3$ 的数据范围？

这确实是我的严重错误；我必须彻底承认自己完全没有任何水平，连自己写出的代码的时间复杂度都不会分析。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int c,T;

int n,m;
ll s,k;
ll w[1005][1005];

ll vis[1005][1005];

queue<int> q;

ll ans;

void solve1(){
	for(int i=1;i<=m;++i){
		vis[0][i]=s;
	}
	for(int i=1;i<n;++i){
		vis[i][0]=vis[i][m+1]=1e18;
		for(int j=1;j<=m;++j){
			vis[i][j]=min(vis[i-1][j]+w[i][j],k);
			if(vis[i][j]<0) vis[i][j]=-1e18;
			else q.push(j);
		}
		while(q.size()){
			int j=q.front();q.pop();
			if(j==0||j==m+1) continue;
			ll ne=min(vis[i][j]+w[i][j-1],k);
			if(ne>=0){
				if(w[i][j]+w[i][j-1]>0&&vis[i][j-1]<min(k+w[i][j-1],k)){
					vis[i][j]=min(k+w[i][j],k);
					vis[i][j-1]=min(k+w[i][j-1],k);
					q.push(j-1),q.push(j);
				}
				else if(ne>vis[i][j-1]){
					vis[i][j-1]=ne;
					q.push(j-1);
				}
			}
			ne=min(vis[i][j]+w[i][j+1],k);
			if(ne>=0){
				if(w[i][j]+w[i][j+1]>0&&vis[i][j+1]<min(k+w[i][j+1],k)){
					vis[i][j]=min(k+w[i][j],k);
					vis[i][j+1]=min(k+w[i][j+1],k);
					q.push(j+1),q.push(j);
				}
				else if(ne>vis[i][j+1]){
					vis[i][j+1]=ne;
					q.push(j+1);
				}
			}
		}
		for(int j=1;j<=m;++j) vis[i][j]=min(vis[i][j],k);
	}
	
	for(int i=1;i<=m;++i){
		ll res=min(vis[n-1][i]+w[n][i],k);
		if(res>=0) ans=max(ans,res);
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	//freopen("journey8.in","r",stdin);
	
	cin>>c>>T;
	
	while(T--){
		cin>>n>>m>>s>>k;
		
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				cin>>w[i][j];
			}
			w[i][0]=w[i][m+1]=-1e18;
		}
		
		ans=-1e18;
		
		solve1();
		
		if(ans>=0) cout<<ans<<endl;
		else cout<<-1<<endl;
	}
	
	
	return 0;
}