蒟蒻求助,改了很久没过
查看原帖
蒟蒻求助,改了很久没过
1059565
liuyinuo666楼主2024/12/24 21:53

rt

#include<bits/stdc++.h>
#define int long long
using namespace std;
priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<>>q;
int ans,h,w,x,sx,sy,a[505][505],vis[505][505];
int fx[]= {1,-1,0,0},fy[]= {0,0,1,-1};
bool in(int x,int y) {
	return x>=1 && x<=h && y>=1 && y<=w;
}
signed main() {
	cin>>h>>w>>x;
	cin>>sx>>sy;
	q.push(make_tuple(0,sx,sy));
	for(int i=1; i<=h; i++) {
		for(int j=1; j<=w; j++) {
			cin>>a[i][j];
		}
	}
	ans=a[sx][sy];
	vis[sx][sy]=1;	for(int i=0; i<4; i++) {
		int nx=sx+fx[i],ny=sy+fy[i];
		if(in(nx,ny)) {
			q.push(make_tuple(a[nx][ny],nx,ny));
			vis[nx][ny]=1;
		}
	}
	while(!q.empty()) {
		auto now=q.top();
		q.pop();
		int x=get<1>(now),y=get<2>(now);
		int t=a[x][y];
		if(t<(ans+x-1)) {
			ans+=t;
			for(int i=0; i<4; i++) {
				int nx=x+fx[i],ny=y+fy[i];
				if(in(nx,ny) && vis[nx][ny]==0) {
					q.push(make_tuple(a[nx][ny],nx,ny));
					vis[nx][ny]=1;
				} 
			}
		} 
		else break;
	}
	cout<<ans;
}
2024/12/24 21:53
加载中...