POJ 2139 Six Degrees of Cowvin Bacon （floyd)

 1 #include <iostream>
 2 #include <vector>
 3 #include <cstring>
 4 #include <cstdio>
 5 using namespace std;
 6 #define INF 0x7ffffff
 7 int G[305][305];
 8 int N,M;
 9 void input()
10 {
11     scanf("%d%d",&N,&M);
12 
13     for(int i=0;i<=N;i++)
14     {
15         for(int j=0;j<=N;j++)
16         {
17             G[i][j] = INF;
18         }
19     }
20     vector<int> v;
21     for(int i=0;i<M;i++)
22     {
23         int n;
24         scanf("%d",&n);
25         for(int i=0;i<n;i++)
26         {
27             int t; scanf("%d",&t);
28             v.push_back(t);
29         }
30         int len = v.size();
31         for(int p=0;p<len;p++)
32         {
33             for(int q=p+1;q<len;q++)
34             {
35                 G[v[p]][v[q]] = G[v[q]][v[p]] = 1;
36             }
37         }
38         v.clear();
39     }
40 }
41 void floyd()
42 {
43 
44     for(int k=1;k<=N;k++)
45     {
46         for(int i=1;i<=N;i++)
47         {
48             for(int j = 1;j<=N;j++)
49             {
50                 if(i!=j)
51                 G[i][j] = min( G[i][j] , G[i][k] + G[k][j]);
52             }
53         }
54     }
55 }
56 
57 void print()
58 {
59     for(int i=1;i<=N;i++)
60     {
61         for(int j=1;j<=N;j++)
62         {
63             cout<<G[i][j]<<‘ ‘;
64         }
65         cout<<endl;
66     }
67 
68 }
69 int main()
70 {
71 
72     input();
73    // print();
74     floyd();
75 
76     double ans = 100000000;
77     for(int i=1;i<=N;i++)
78     {
79             int deg = 0 , cnt =0;
80             for(int j=1;j<=N;j++)
81             {
82                 if( i == j)continue;
83 
84                 if( G[i][j] != INF)
85                 {
86                     deg += G[i][j];
87                     cnt++;
88                 }
89             }
90             if( ans > deg*1.0/cnt)
91             {
92                 ans = deg*1.0/cnt;
93             }
94     }
95     cout<<int(ans*100)<<endl;
96     return 0;
97 }