优先队列广搜样板
2024-07-29 21:30:22
发布于：浙江
62阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
struct Node{
int x,y;
int val;
friend bool operator < (Node a,Node b){
return a.val > b.val; // 价值较小的先出队列
}
};
priority_queue<Node> q;
bool vis[1005][1005];
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
int mp[1005][1005];
int n,sx,sy,ex,ey;
int bfs()
{
q.push({sx,sy,mp[sx][sy]});
vis[sx][sy] = true;
while(!q.empty())
{
Node fr = q.top();
q.pop();
if(fr.x == ex && fr.y == ey) return fr.val;
for(int i = 0 ; i < 4 ; i ++ )
{
int tx = fr.x + dir[i][0];
int ty = fr.y + dir[i][1];
if(tx > n || ty > n || tx < 1 || ty < 1)continue;
if(vis[tx][ty])continue;
vis[tx][ty] = true;
q.push({tx,ty,fr.val + mp[tx][ty]});
}
}
}
int main()
{
freopen("gc.in","r",stdin);
freopen("gc.out","w",stdout);
cin >> n >> sx >> sy >> ex >> ey;
for(int i = 1 ; i <= n ; i ++ ){
for(int j = 1 ; j <= n ; j ++ )
{
cin >> mp[i][j];
}
}
cout << bfs() << endl;
fclose(stdin);
fclose(stdout);
return 0;
}
有帮助，赞一个