1
2026-02-03 11:35:53
发布于：北京
5阅读
0回复
0点赞
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3+10;
long long a[N][N],n,m,w,dis[N][N],vis[N][N],ans = 1e18,cnt1 = 1e18,cnt2 = 1e18;
struct node{
long long x,y;
};
int dx[] = {1,0,0,-1};
int dy[] = {0,1,-1,0};
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> w;
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
cin >> a[i][j];
queue <node> q;
q.push({1,1});
vis[1][1] = 1;
while(q.size()){
node u = q.front();
q.pop();
if(u.x == n && u.y == m)
ans = dis[n][m];
for(int i = 0;i < 4;i++){
int xx = u.x+dx[i],yy = u.y+dy[i];
if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && a[xx][yy] != -1 && !vis[xx][yy]){
vis[xx][yy] = 1;
dis[xx][yy] = dis[u.x][u.y]+w;
if(a[xx][yy] > 0)
cnt1 = min(cnt1,dis[xx][yy]+a[xx][yy]);
q.push({xx,yy});
}
}
}
q.push({n,m});
memset(vis,0,sizeof vis);
vis[n][m] = 1;
memset(dis,0,sizeof dis);
while(q.size()){
node u = q.front();
q.pop();
for(int i = 0;i < 4;i++){
int xx = u.x+dx[i],yy = u.y+dy[i];
if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && a[xx][yy] != -1 && !vis[xx][yy]){
vis[xx][yy] = 1;
dis[xx][yy] = dis[u.x][u.y]+w;
if(a[xx][yy] > 0)
cnt2 = min(cnt2,dis[xx][yy]+a[xx][yy]);
q.push({xx,yy});
}
}
}
// cout << cnt1 << " " << cnt2 << " " << ans << endl;
long long xxx = min(cnt1+cnt2,ans);
if(xxx == 1e18)
cout << -1;
else
cout << xxx;
return 0;
}
这里空空如也
有帮助，赞一个