Six Degrees of Cowvin Bacon | Time Limit: 1000MS | | Memory Limit: 65536K |
| Total Submissions: 3982 | | Accepted: 1870 |
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 23 1 2 32 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
分析：bellman的模板题目，稍微有点价值的就是多源最短路径的处理 #include #include #include #include using namespace std; #define inf 0x3f3f3f3f int dist[305][305],a[305]; int n,m,num,cnt; struct Edge{ int f,t,c; }edge[1005]; void init() { memset(dist,0x3f,sizeof(dist)); for(int i=1;i<=1003;i++) edge[i].c=inf; cnt=0; for(int i=1;i<=n;i++) dist[i][i]=0; //注意dist[i][i]要初始化为0 } void bellman() { for(int s=1;s<=n;s++) //多源最短路径的处理，在模板中单个起点的while循环外嵌套一层不同起点的循环,同时dist改为二维 { while(1) { bool flag=false; for(int j=1;j<=cnt;j++) { int from=edge[j].f,to=edge[j].t,cost=edge[j].c; if(dist[s][to]>dist[s][from]+cost) { dist[s][to]=dist[s][from]+cost; flag=true; } } if(!flag) break; } } int minn=inf,w; for(int i=1;i<=n;i++) { w=0; for(int j=1;j<=n;j++) w+=dist[i][j]; if(w