7-36 社交网络图中结点的“重要性”计算 (30 分) 不用迪杰斯特拉也不用弗洛伊德

原题：https://pintia.cn/problem-sets/15/problems/863

这种无权图的最短路径直接用类似于BFS的思路就可以计算了；

#include<iostream>
#include<queue> 
#define MAXSIZE 10010
#define inf 666666666
using namespace std;
int N,M,K;
int FLAG=1;
int G[MAXSIZE][MAXSIZE];
int dist[MAXSIZE];//距离 
void unweight(int x)//无权图的最短路径
{
	int i;
	queue<int>q;	
	for(i=1;i<=N;i++)dist[i]=-1;//初始化为-1
	q.push(x);	//入队
	dist[x]=0;//并且自己到自己距离为0
	while(!q.empty())
	{
		int v=q.front();
		q.pop();

		for(i=1;i<=N;i++)
		{
			if(dist[i]==-1&&G[v][i]==1)//只要是-1的就说明还未访问过,并且v和I直接有边
			{
				dist[i]=dist[v]+1;//直接加1就行了		
				q.push(i);	//记得入队
			}
		}
	}
}
int main()
{
	int i,j;
	double sum=0.0;
	scanf("%d%d",&N,&M);
	for(i=1;i<=M;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		G[x][y]=G[y][x]=1;		
	}
	scanf("%d",&K);
	for(i=0;i<K;i++)
	{
		int x;
		scanf("%d",&x);
		unweight(x);//计算最短路径 
		for(j=1;j<=N;j++)
		{
			if(j==x)continue;
			if(dist[j]==-1)
			{
			FLAG=0;	break;
			}
			sum+=dist[j];
		}
		if(FLAG==1)
		{
		sum/=(N-1);
		printf("Cc(%d)=%.2f\n",x,1/sum);	
		}
		else
		printf("Cc(%d)=0.00\n",x);		
		sum=0;
	}
	
	return 0;
}