PAT6-09. 社交网络图中结点的“重要性”计算_7-1 社交网络图中结点的“重要性”计算 (70 分)

用bfs计算无权图的最短路径

#include<queue>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<bitset>
using namespace std;
const int N=10005,INF=1<<30;
vector<int> adj[N];
int n,m;
 
double bfs(int k){
  bitset<N>used;
  int dis[N];fill_n(dis,N,INF);dis[k]=0;
  queue<int>Q; Q.push(k);used.set(k);
  while(Q.size()){
    int ft=Q.front();Q.pop();
    for(auto x:adj[ft])
      if(!used[x]){
	used.set(x);
	Q.push(x);
	dis[x]=dis[ft]+1;
      }//for
  }//while
  double ret(0.0);
  for(int i=1;i<=n;++i)
    if(dis[i]==INF)return 0.0;
    else ret+=dis[i];
  return (n-1)/ret;
}
int main(){
  scanf("%d%d",&n,&m);
  while(m--){
    int a,b;scanf("%d%d",&a,&b);
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  int cnt;scanf("%d",&cnt);
  while(cnt--){
    int k;scanf("%d",&k);
    printf("Cc(%d)=%.2lf\n",k,bfs(k));
  }
}