http://poj.org/problem?id=2139
六度空间：为了向“六度分割：你和任何一个陌生人之间所间隔的人不会超过五个”致敬，奶牛们决定拍一系列电影叫做……《六度空间》。N头牛，拍了M部电影，同一部电影中的搭档们距离1，求最小度数之和。
2.5 它们其实都是“图”
最短路
很水很基础的Floyd-Warshall算法：
Read full article from 2139 -- Six Degrees of Cowvin Bacon
Description
The cows have been making movies lately, so they are ready to play a variant of the famous game "Six Degrees of Kevin Bacon".
The game works like this: each cow is considered to be zero degrees of separation (degrees) away from herself. If two distinct cows have been in a movie together, each is considered to be one 'degree' away from the other. If a two cows have never worked together but have both worked with a third cow, they are considered to be two 'degrees' away from each other (counted as: one degree to the cow they've worked with and one more to the other cow). This scales to the general case.
The N (2 <= N <= 300) cows are interested in figuring out which cow has the smallest average degree of separation from all the other cows. excluding herself of course. The cows have made M (1 <= M <= 10000) movies and it is guaranteed that some relationship path exists between every pair of cows.
The game works like this: each cow is considered to be zero degrees of separation (degrees) away from herself. If two distinct cows have been in a movie together, each is considered to be one 'degree' away from the other. If a two cows have never worked together but have both worked with a third cow, they are considered to be two 'degrees' away from each other (counted as: one degree to the cow they've worked with and one more to the other cow). This scales to the general case.
The N (2 <= N <= 300) cows are interested in figuring out which cow has the smallest average degree of separation from all the other cows. excluding herself of course. The cows have made M (1 <= M <= 10000) movies and it is guaranteed that some relationship path exists between every pair of cows.
Input
* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Each input line contains a set of two or more space-separated integers that describes the cows appearing in a single movie. The first integer is the number of cows participating in the described movie, (e.g., Mi); the subsequent Mi integers tell which cows were.
* Lines 2..M+1: Each input line contains a set of two or more space-separated integers that describes the cows appearing in a single movie. The first integer is the number of cows participating in the described movie, (e.g., Mi); the subsequent Mi integers tell which cows were.
Output
* Line 1: A single integer that is 100 times the shortest mean degree of separation of any of the cows.
Sample Input
4 2 3 1 2 3 2 3 4
Sample Output
100http://blog.csdn.net/yew1eb/article/details/29187075
题意：给定牛的关系图，求其中一头牛与其他牛关系路程之和sum最小，然后输出 sum*100/(n-1)
floyd求任意两点间的最短路程
注意： inf不能太大，因为 f[i][k] + f[k][j] 做加法时可能会溢出！
http://www.hankcs.com/uncategorized/poj-2139-six-degrees-of-cowvin-bacon.html六度空间：为了向“六度分割：你和任何一个陌生人之间所间隔的人不会超过五个”致敬，奶牛们决定拍一系列电影叫做……《六度空间》。N头牛，拍了M部电影，同一部电影中的搭档们距离1，求最小度数之和。
2.5 它们其实都是“图”
最短路
很水很基础的Floyd-Warshall算法：
int d[MAX_V][MAX_V]; // d[u][v]表示边e=(u,v)的权值，不存在的时候等于无穷大或者d[i][i] = 0int V; // 顶点数int x[MAX_V];void warshall_floyd(){ for (int k = 0; k < V; ++k) { for (int i = 0; i < V; ++i) { for (int j = 0; j < V; ++j) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } }}int main(int argc, char *argv[]){#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);#endif int M; cin >> V >> M; memset(d, 0x3f, sizeof(d)); for (int i = 0; i < V; ++i) { d[i][i] = 0; } while (M--) { int n; cin >> n; for (int i = 0; i < n; ++i) { cin >> x[i]; --x[i]; } for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { d[x[i]][x[j]] = d[x[j]][x[i]] = 1; } } } warshall_floyd(); int ans = 0x3f3f3f3f; for (int i = 0; i < V; ++i) { int sum = 0; for (int j = 0; j < V; ++j) { sum += d[i][j]; } ans = min(ans, sum); } cout << 100 * ans / (V - 1) << endl;#ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); system("out.txt");#endif return 0;}