社区讨论

RE求调

P2895[USACO08FEB] Meteor Shower S参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@m43z9pp9
此快照首次捕获于
2024/11/30 17:36
去年
此快照最后确认于
2025/11/04 13:35
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
int m; 
struct note{
	int x, y, t;
};
note a[100000];
int cnt = -1;
int dx[5] = {0, 0, 1, 0, -1};
int dy[5] = {0, 1, 0, -1, 0};
int flag[500][500];
int dt[500][500];
void bfs(int xx, int yy, int tt){
	queue<note> q;
	flag[xx][yy] = 1;
	q.push((note){xx, yy, tt});
	while(!q.empty()){
		note to = q.front();
		q.pop();
		if(dt[to.x][to.y] == 1e9) {
			cnt = to.t;
			break;
		}
		for(int i = 1; i <= 4; i++){
			int xxx = to.x+dx[i];
			int yyy = to.y+dy[i];
			if(xxx >= 0 && yyy >= 0 && !flag[xxx][yyy] && to.t+1 < dt[xxx][yyy]){
				q.push((note){xxx, yyy, to.t+1});
//				cout << xxx << " " << yyy << " " << to.t+1 << endl;
				flag[xxx][yyy] = 1;
			}
		}
	}
}
int main(){
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	cin>>m;
	for(int i = 0; i <= 400; i++){
		for(int j = 0; j <= 400; j++){
			dt[i][j] = 1e9;
		}
	}
	for(int i = 1; i <= m; i++){
		cin >> a[i].x >> a[i].y >> a[i].t;
		dt[a[i].x][a[i].y] = a[i].t;
		for(int j = 1; j <= 4; j++){
			dt[a[i].x+dx[j]][a[i].y+dy[j]] = a[i].t;
		}
	}
	bfs(0, 0, 0);
	cout << cnt;
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...