7-36 社交网络图中结点的“重要性”计算 (30分)-floyd最短路径

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <iomanip>
 4 #define infinity 65535
 5 using namespace std;
 6 int D[10001][10001];//储存最短路径
 7     int N;
 8     long int M;
 9 int main()
10 {
11     
12     cin >> N >> M;
13     for(int i=1;i<=N;i++)
14         for (int j = 1; j <= N; j++)
15         {
16             D[i][j] = infinity;
17         }
18     for (int i = 0; i < M; i++) 
19     {
20         int a, b;
21         cin >> a >> b;
22         D[a][b]= D[b][a] = 1;
23     }
24 //floyd算法
25     for(int k=1;k<=N;k++)
26         for(int i=1;i<=N;i++)
27             for (int j = 1; j <= N;j++)
28             {
29                 if (i == j || i == k || j == k)continue;
30                 if (D[i][k] + D[k][j] < D[i][j])
31                 {
32                     D[i][j] =D[j][i]= D[i][k] + D[k][j];
33                 }
34             }
35     int n;
36     cin >> n;
37     int flag=0;
38     for (int i = 0; i < n; i++)
39     {
40         int x;
41         double sum=0;
42         cin >> x;
43             for (int k = 1; k <= N; k++)
44             {
45                 if(x==k)continue;
46                 if(flag==1)break;
47                 if(D[x][k]==infinity)
48                 {
49                    flag =1;
50                    break;
51                 }
52                 else sum += D[x][k];
53             }
54             if(flag)//如果是非连通图
55             cout << setprecision(2) << fixed << "Cc(" << x << ")=" << "0.00"<<endl;
56             else cout << setprecision(2) << fixed << "Cc(" << x << ")=" << (N - 1.0) / sum <<endl;
57     }
58     return 0;
59 }