题目链接：点击打开链接
题目大意：略。
解题思路
1、是否连通图：是，则继续2、3；否，则输出“0.00”。
2、所求的结点出发到其余的结点的最少边数（最短距离）的总和。
3、（n-1）/ 第2步的结果。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=1e4+100; struct node { int u,step; }; int vis[maxn]; int sum,cnt; vector<int> vec[maxn]; void bfs(int u) { node nd; nd.u=u; nd.step=0; queue<node> q; q.push(nd); cnt++; vis[u]=1; while(!q.empty()) { node fnt=q.front(); q.pop(); for(int i=0;i<vec[fnt.u].size();i++) { if(!vis[vec[fnt.u][i]]) { vis[vec[fnt.u][i]]=1; nd.u=vec[fnt.u][i]; nd.step=1+fnt.step; sum+=nd.step; cnt++; q.push(nd); } } } return; } int main() { int n,m,l,u,v; while(~scanf("%d%d",&n,&m)) { for(int i=0;i<m;i++) { scanf("%d%d",&u,&v); vec[u].push_back(v); vec[v].push_back(u); } scanf("%d",&l); while(l--) { mem(vis,0); sum=cnt=0; scanf("%d",&u); bfs(u); if(cnt==n) printf("Cc(%d)=%.2f\n",u,(n-1)*1.0/sum); else printf("Cc(%d)=0.00\n",u); } } return 0; }
