倒计时
2023-07-31 09:16:05
发布于：浙江
2小时
全部评论 2
#include<bits/stdc++.h>
using namespace std;
int n,m,vis[1005][1005],a[1005][1005],ans;
int vx[]={1,0};
int vy[]={0,1};
int ex[]={-1,0};
int ey[]={0,-1};
struct node
{
int x,y,t;
friend bool operator<(node f1,node f2) {
return f1.t<f2.t;
}
};
priority_queue <node> q;
void bfs_first()
{
while(!q.empty())
{
node s=q.top();
q.pop();
if(s.xn && s.ym) {
ans=s.t;
break;
}
for(int i=0;i<2;i++)
{
int nx=s.x+vx[i];
int ny=s.y+vy[i];
if(nx<=n && nx>=1 && ny<=m && ny>=1 && vis[nx][ny]0) {
q.push({nx,ny,s.t+a[nx][ny]});
vis[nx][ny]=1;
}
}
}
while (!q.empty()) {//释放未选择的路
node s=q.top();
vis[s.x][s.y]=0;
q.pop();
}
}
void bfs_second()
{
while(!q.empty())
{
node s=q.top();
q.pop();
if(s.x1 && s.y==1) {
ans=s.t;
break;
}
for(int i=0;i<2;i++)
{
int nx=s.x+ex[i];
int ny=s.y+ey[i];
if(nx<=n && nx>=1 && ny<=m && ny>=1 && vis[nx][ny]==0) {
q.push({nx,ny,s.t+a[nx][ny]});
vis[nx][ny]=1;
}
}
}
}
int main()
{
cin>>m>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
vis[1][1]=1;
q.push({1,1,0});
bfs_first();
vis[1][1]=0;
q.push({n,m,ans});
bfs_second();
cout<<ans;
return 0;
}2024-08-18 来自 浙江
0
有帮助，赞一个