社区讨论
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 条回复,欢迎继续交流。
正在加载回复...