Six Degrees of Cowvin Bacon
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 131072/65536K (Java/Other)
Total Submission(s) : 2 Accepted Submission(s) : 1
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.
<br> <br>* 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.
<br>
shortest mean degree of separation of any of the cows. <br>
3 1 2 3
2 3 4
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#define inf 0x3f3f3f3f
using namespace std;
int e[][];
int n, m;
int main()
{
int n, m;
cin >> n >> m;
int i, j;
int a[];
for (i = ; i <= n; i++)
{
for (j = ; j <= n; j++)
{
if (i == j) e[i][j] = ;
else e[i][j] = inf;
}
}
for (i = ; i <= m; i++)
{
int k,p;
cin >> k;
for (j = ; j <= k; j++)
{
cin >> a[j];
}
for (j = ; j <= k; j++)
{
for (p = j+; p <= k; p++)
{
e[a[j]][a[p]] = ;
e[a[p]][a[j]] = ;
}
}
}
int k;
for (k = ; k <= n; k++)
{
for (i = ; i <= n; i++)
{
for (j = ; j <= n; j++)
{
if (e[i][j] > e[i][k] + e[k][j])
e[i][j] = e[i][k] + e[k][j];
}
}
}
int ans = inf;
int sum = ;
for (i = ; i <= n; i++)
{
sum = ;
for (j = ; j <= n; j++)
{
if (e[i][j] != inf)
{
sum += e[i][j];
}
}
if (sum < ans) ans = sum;
}
ans= ans*/ (n-) ;
cout <<ans<< endl;
}