题目传送门
Six Degrees of Cowvin Bacon
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 6179 Accepted: 2893
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.
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.
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
100
Hint
[Cow 3 has worked with all the other cows and thus has degrees of separation: 1, 1, and 1 – a mean of 1.00 .]
Source
USACO 2003 March Orange
题意：
牛跟自己的分离度是0，如果两牛合作分离度则为1，如果两牛同时和第三头牛合作分离度为2.求一头牛到其他牛最小的平均分离度，即求最短路。
我个人比较喜欢用Dijkstra求最短路，虽然这个题目用floyd也可以，也更加方便，不过我还是用Dijkstra敲的代码。
基础最短路问题
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
typedef pair<int,int>P;
const int maxn=500;
const int INF=0x3f3f3f3f;
struct Edge{int to,len;Edge(int to_=0,int len_=0){to=to_;len=len_;}
};
vector<Edge>G[maxn];
int dis[maxn];
bool vis[maxn];
int n,m;
void init()
{for(int i=1;i<=n;i++)G[i].clear();
}
void Add(int from,int to,int len)
{G[from].push_back(Edge(to,len));G[to].push_back(Edge(from,len));
}
void Dijkstra(int s)
{fill(dis,dis+n+1,INF);dis[s]=0;memset(vis,false,sizeof(vis));priority_queue<P,vector<P>,greater<P> >que;int u,v,i,len;Edge e;P p;que.push(P(0,s));while(!que.empty()){p=que.top();que.pop();u=p.second;if(vis[u])continue;vis[u]=true;len=G[u].size();for(int i=0;i<len;i++){e=G[u][i];v=e.to;if(!vis[v]&&dis[v]>dis[u]+e.len){dis[v]=dis[u]+e.len;que.push(P(dis[v],v)); } }}
}
int main()
{while(scanf("%d%d",&n,&m)==2){init();for(int i=0;i<m;i++){int k,ans[maxn],tot;scanf("%d",&k);tot=k;while(k--){scanf("%d",&ans[k]);}for(int i=0;i<tot;i++){for(int j=0;j<tot;j++){if(i==j)continue;Add(ans[i],ans[j],1);}}}int Min=INF;for(int i=1;i<=n;i++){Dijkstra(i);int len_sum=0;for(int i=1;i<=n;i++)len_sum+=dis[i];if(Min>len_sum)Min=len_sum;}printf("%d\n",Min*100/(n-1));}
}