BZOJ 3402: [Usaco2009 Open]Hide and Seek 捉迷藏(最短路)

这个= =一看就是最短路了= =

PS：最近有点懒 = = 刚才看到一道平衡树的裸题还嫌懒不去写= =算了等刷完这堆水题再去理= =

CODE：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
#define maxm 100010
#define maxn 20020
struct edges{
int to,next;
}edge[maxm];
int next[maxn],l;
int addedge(int x,int y){
edge[++l]=(edges){y,next[x]};next[x]=l;
edge[++l]=(edges){x,next[y]};next[y]=l;
return 0;
}
int dist[maxn],n,m;
bool b[maxn];
queue<int>q;
#define inf 0x7fffffff
int spfa(){
for (int i=1;i<=n;i++) dist[i]=inf;
dist[1]=0;
q.push(1);
while (!q.empty()){
  int u=q.front();q.pop();
  b[u]=0;
  for (int i=next[u];i;i=edge[i].next)
   if (dist[edge[i].to]>dist[u]+1){
    dist[edge[i].to]=dist[u]+1;
    if (!b[edge[i].to]) {
     q.push(edge[i].to);
     b[edge[i].to]=1;
    }
   }
}
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++) {
  int x,y;
  scanf("%d%d",&x,&y);
  addedge(x,y);
}
spfa();
int ans=0,sum=0;
for (int i=2;i<=n;i++) {
  if (dist[i]>dist[ans]) ans=i,sum=0;
  if (dist[i]==dist[ans]) sum++;
}
printf("%d %d %d",ans,dist[ans],sum);
return 0;
}

巴特西

BZOJ 3402: [Usaco2009 Open]Hide and Seek 捉迷藏(最短路)

最新文章

热门文章