POJ 2139 - Six Degrees of Cowvin Bacon

http://poj.org/problem?id=2139

概要

N 頭の牛に関して，M 本の各映画について，それぞれどの牛が出演したかの情報が与えられる．

同じ映画にある2頭の牛が出演したとき，互いに「1 degree away」であるという． 同じ映画に出演したことはないが，どちらもある別の牛となら同じ映画に出演したことがあるなら，互いに「2 degree away」といい，以降同様に degree を定める．

degree の平均が最も小さい牛に興味がある．その牛の degree の平均値の100倍の値を整数値(切り捨て)で答える．

制約

解法

ワーシャルフロイドするだけ．

 1 #include <cstdio>
 2 #include <vector>
 3 #include <limits>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8   int N, M;
 9   scanf("%d %d", &N, &M);
10   vector<vector<int> > dist(N, vector<int>(N, 1000000));
11   for (int i = 0; i < M; i++) {
12     int n;
13     scanf("%d", &n);
14     vector<int> v(n);
15     for (int j = 0; j < n; j++) {
16       scanf("%d", &v[j]);
17       --v[j];
18     }
19     for (int j = 0; j < n; j++) {
20       for (int k = 0; k < n; k++) {
21         if (j != k) {
22           dist[v[j]][v[k]] = 1;
23         }
24       }
25     }
26   }
27 
28   for (int k = 0; k < N; k++) {
29     for (int i = 0; i < N; i++) {
30       for (int j = 0; j < N; j++) {
31         dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
32       }
33     }
34   }
35 
36   int m = numeric_limits<int>::max();
37   for (int i = 0; i < N; i++) {
38     int s = 0;
39     for (int j = 0; j < N; j++) {
40       if (i != j) {
41         s += dist[i][j];
42       }
43     }
44     m = min(m, s);
45   }
46   printf("%d\n", (100*m)/(N-1));
47   return 0;
48 }
poj/2139.cc