poj 2139 Six Degrees of Cowvin Bacon 最短路

缘起

日常浪费生命 poj 2139 Six Degrees of Cowvin Bacon

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
有n头牛，总共拍摄了m部电影.牛到自己距离是0， 如果两头牛同拍一部电影，这他们之间的距离为一，如果两头牛都和第三头牛拍过同一部电影，那么它们之
间的距离经第三头牛传递就为2，以此类推，求哪一头牛与其它牛距离的平均值最小，把他乘一百输出。（求的时候，先扩大一百倍再求平均值）

【输入】
第一行是两个整数N和M (2 <= N <= 300, 1 <= M <= 10000)
后面M行，每行第一个整数表示有多少头牛参与了此部电影的拍摄, 后面就是参与的牛的标号.

【输出】
结果

【样例输入】
4 2
3 1 2 3
2 3 4

【样例输出】
100

【限制】
1s

【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 .]

因为n较小，所以可以使用floyd. 但是先将距离扩大一百倍.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL

int n,m,g[305][305],s[305];

void floyd()
{
	for (int k = 1; k<=n;k++)
	{
		for (int i = 1; i<=n; i++)
		{
			for (int j = 1; j<=n; j++)
			{
				g[i][j] = min(g[i][j], g[i][k]+g[k][j]);
			}
		}
	}
}


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &n, &m);
	memset(g, 0x3f, sizeof(g));
	for (int i =1;i<=n;i++)
	{
		g[i][i] = 0;
	} // 初始化
	while(m--)
	{
		int num;
		scanf("%d", &num);
		for (int i = 1;i<=num; i++)
		{
			scanf("%d", s+i);
		}
		for (int i = 1;i<=num; i++)
		{
			for (int j = i+1;j<=num; j++)
			{
				g[s[i]][s[j]] = g[s[j]][s[i]] =100; // 乘以100
			}
		}
	}
	floyd();
	int ans = 0x3f3f3f3f;
	for (int i = 1,sum;i<=n; i++) //开始枚举每头牛
	{
		sum =0;
		for (int j = 1; j<=n;j++)
		{
			sum+=g[i][j];
		}
		if (ans>sum/(n-1))
		{
			ans = sum/(n-1);
		}
	}
	printf("%d\n", ans);
	return 0;
}

ac情况

Status Accepted
Memory 448kB
Length 1005
Lang C++
Submitted 2019-08-30 12:04:05
Shared
RemoteRunId 20818407