描述
母牛最近一直在拍电影，所以他们准备玩一个著名游戏“六度凯文培根”的变体。
游戏的工作原理是这样的：每头母牛都被认为与自己的距离为零。如果一部电影里有两只不同的母牛在一起，那么每只母牛都被认为是一个“度”之外的另一头。如果一只两头牛从来没有一起工作过，但都和第三头母牛一起工作过，那么它们被认为是相隔两度的(计算为：与它们一起工作的母牛有一个度，对另一头母牛来说是多一个度)。这符合一般情况。
N(2<=N<=300)奶牛感兴趣的是找出哪头牛与其他奶牛的平均分离程度最小。当然不包括她自己。奶牛制作了M(1<=M<=10000)电影，保证了每一对奶牛之间存在一定的关系路径。
输入
*第1行：两个空格分隔的整数：n和M
*第2行…m+1：每个输入行包含一组由两个或多个空格分隔的整数组成的集合，这些整数描述一部电影中出现的奶牛。第一个整数是参与所描述的电影的奶牛数量(例如，Mi)；随后的Mi整数判断哪些奶牛是奶牛。
输出量
第1行：一个整数，是任何奶牛的最短平均分离度的100倍。
样本输入
4 2
3 1 2 3
2 3 4
样本输出
100
该题的意思就是求几个牛中的一头与其他牛距离的平均值最小的牛
代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<vector>
#include<set>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
#include<sstream>
#include<memory>
#include<functional>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a));
#define ll long long int
const int INF=0x3f3f3f3f;
int n,m;
int a[310];
int map1[310][310],vis[310],dis[310];
void dijkstra(int x)//dijkstra板子
{int i,j,min1,t;for(i=1;i<=n;i++){dis[i]=map1[x][i];//初始化vis[i]=0;//所有点未访问过,初始化}vis[x]=1;//从1开始for(i=1;i<=n;i++){min1=0x3f3f3f3f;for(j=1;j<=n;j++){if(vis[j]==0&&dis[j]<min1)//如果j点未被访问，且以该方法到j点距离小于当前最小距离（min1）则改变最小距离{t=j;min1=dis[j];}}vis[t]=1;//t点被访问了for(j=1;j<=n;j++){if(vis[j]==0&&dis[t]+map1[t][j]<dis[j])//如果i点未被访问且有已有路程加上t点到i点的距离小于从之前点直接到i点距离那么选择经过t点到达i点dis[j]=dis[t]+map1[t][j];}}
}
int main()
{int js,i,j;mem(map1,INF);cin>>n>>m;while(m--){int js;cin>>js;for(i=0;i<js;i++)cin>>a[i];for(i=0;i<js;i++)for(j=i+1;j<js;j++){if(a[i]!=a[j])map1[a[i]][a[j]]=map1[a[j]][a[i]]=1;}}double min1=0x3f3f3f;for(i=1;i<=n;i++){double sum=0;mem(vis,0);//只需初始化vis里的就可以，dis在dijkstra板子里会初始化dijkstra(i);for(j=1;j<=n;j++){if(i!=j)sum+=dis[j];}min1=min(min1,sum/(n-1));//就是求几个牛中的一头与其他牛距离的平均值最小的牛}cout<<int(min1*100)<<endl;
}