7-12（圖） 社交網絡圖中結點的“重要性”計算（30 分）

在社交網絡中，個人或單位（結點）之間通過某些關系（邊）聯系起來。他們受到這些關系的影響，這種影響可以理解為網絡中相互連接的結點之間蔓延的一種相互作用，可以增強也可以減弱。而結點根據其所處的位置不同，其在網絡中體現的重要性也不盡相同。

“緊密度中心性”是用來衡量一個結點到達其它結點的“快慢”的指標，即一個有較高中心性的結點比有較低中心性的結點能夠更快地（平均意義下）到達網絡中的其它結點，因而在該網絡的傳播過程中有更重要的價值。在有N個結點的網絡中，結點v?i??的“緊密度中心性”Cc(v?i??)數學上定義為v?i??到其余所有結點v?j?? (j≠i) 的最短距離d(v?i??,v?j??)的平均值的倒數：

對于非連通圖，所有結點的緊密度中心性都是0。

給定一個無權的無向圖以及其中的一組結點，計算這組結點中每個結點的緊密度中心性。

輸入格式:

輸入第一行給出兩個正整數N和M，其中N（≤10?4??）是圖中結點個數，順便假設結點從1到N編號；M（≤10?5??）是邊的條數。隨后的M行中，每行給出一條邊的信息，即該邊連接的兩個結點編號，中間用空格分隔。最后一行給出需要計算緊密度中心性的這組結點的個數K（≤100）以及K個結點編號，用空格分隔。

輸出格式:

按照Cc(i)=x.xx的格式輸出K個給定結點的緊密度中心性，每個輸出占一行，結果保留到小數點后2位。

輸入樣例:

9 14
1 2
1 3
1 4
2 3
3 4
4 5
4 6
5 6
5 7
5 8
6 7
6 8
7 8
7 9
3 3 4 9

輸出樣例:

Cc(3)=0.47
Cc(4)=0.62
Cc(9)=0.35
解析：這個題如果掌握迪杰斯特拉算法并不難，希望同學們好好看課本，
我還是變參考課本邊做的，有個難點就是，你如果想偷懶，靜態分配一個
a【n】【n】的數組，那么肯定會數組太大直接崩掉，所以動態分配就好了，
（希望僅供參考，不要直接復制到作業）
代碼：

#include<iostream>
#include<cstring>
#include<string>
#include<bits/stdc++.h>
#include<cstdio>
#include<cmath>
#define maxn 10001
using namespace std;
int n,m;
int d[maxn],visit[maxn];
int Dijkstra(int *a[],int v){for(int i=1;i<=n;i++){visit[i]=0;d[i]=a[v][i];}visit[v]=1;d[v]=0;int sum=0;int x;for(int k=1;k<=n;k++){int min=maxn;for(int w=1;w<=n;w++)if(!visit[w]&&d[w]<min){x=w;min=d[w];}visit[x]=1;for(int w=1;w<=n;w++){if(!visit[w]&&d[x]+a[x][w]<d[w]){d[w]=d[x]+a[x][w];}}}for(int i=1;i<=n;i++){if(d[i]==maxn)return -1;sum+=d[i];//cout<<"@@@@@@@@@"<<d[i]<<endl;
    }return sum;
}int main(){
int x,y;
scanf("%d%d",&n,&m);
int **a=(int**)malloc(sizeof(int*)*(n+1));for(int i=1; i<=n; i++) {a[i]=(int*)malloc(sizeof(int)*(n+1));}for(int i=1;i<=n;i++){d[i]=maxn;for(int j=1;j<=n;j++){a[i][j]=maxn;}
}//輸入
for(int i=1;i<=m;i++){cin>>x>>y;a[x][y]=a[y][x]=1;
}
int k;
cin>>k;int v;
for(int i=0;i<k;i++){cin>>v;int su=  Dijkstra(a,v);if(su==-1) printf("Cc(%d)=%.2lf\n",v,0.00);elseprintf("Cc(%d)=%.2lf\n",v,(n-1)*1.0/su*1.0);
}return 0;}

?