poj2139 Six Degrees of Cowvin Bacon

思路：
floyd
实现：
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <vector>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 int a[305][305], n, m, k;
 9 const int INF = 0x3f3f3f3f;
10 int main()
11 {
12     memset(a, 0x3f, sizeof(a));
13     cin >> n >> m;
14     for (int i = 0; i < m; i++)
15     {
16         vector<int> l;
17         int tmp;
18         cin >> k;
19         for (int j = 0; j < k; j++)
20         {
21             cin >> tmp;
22             l.push_back(tmp);
23         }
24         for (int p = 0; p < k; p++)
25         {
26             for (int q = 0; q < k; q++)
27             {
28                 a[l[p]][l[q]] = p == q ? 0 : 1;
29             }
30         }
31     }
32     for (int k = 1; k <= n; k++)
33     {
34         for (int i = 1; i <= n; i++)
35         {
36             for (int j = 1; j <= n; j++)
37             {
38                 if (a[i][k] + a[k][j] < a[i][j])
39                 {
40                     a[i][j] = a[i][k] + a[k][j];
41                 }
42             }
43         }
44     }
45     double __ = INF;
46     for (int j = 1; j <= n; j++)
47     {
48         int sum = 0;
49         for (int k = 1; k <= n; k++)
50         {
51             sum += a[j][k];
52         }
53         double ans = sum * 1.0 / (n - 1);
54         __ = min(ans, __);
55     }
56     cout << (int)(__ * 100) << endl;
57     return 0;
58 }