社区讨论

70分bfs3点RE

P2951[USACO09OPEN] Hide and Seek S参与者 2已保存回复 2

讨论操作

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

当前回复
2 条
当前快照
1 份
快照标识符
@mhjtm7vt
此快照首次捕获于
2025/11/04 08:18
4 个月前
此快照最后确认于
2025/11/04 08:18
4 个月前
查看原帖
rt:
CPP
#include <bits/stdc++.h>
#define SACRIFICING using
#define THE namespace
#define ROOK std
SACRIFICING THE ROOK;
typedef long long ll;
int n,m;
struct node{
	vector<int>s;
}a[20009];
int vis[20009];
bool isin[20009];
queue<int>q;
void bfs(){
	q.push(1);
	isin[1]=1;
	while(!q.empty()){
		int cur=q.front();
		q.pop();
		isin[cur]=0;
		for(int i:a[cur].s){
			if(vis[i]>vis[cur]+1&&isin[i]==0){
				isin[i]=1;
				q.push(i);
			}
            vis[i]=min(vis[i],vis[cur]+1);
		}
	}
}
int maxn=0,ji,sum;
int x,y;
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
        cin>>x>>y;
		a[x].s.push_back(y);
		a[y].s.push_back(x);
        vis[i]=2147483600;
        isin[i]=0;
	}
    vis[1]=0;
	bfs();
	for(int i=1;i<=n;i++){
		if(vis[i]>maxn){
			maxn=vis[i];
			ji=i;	
		}
	}
	for(int i=1;i<=n;i++){
		sum+=(vis[i]==maxn);
	}
	cout<<ji<<' '<<maxn<<' '<<sum;
	return 0;
}
由于做的时候没想到bfs按层遍历,但加上优化全员MLE(三个点还是RE)

回复

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

正在加载回复...