2567554_ac_15ms_196k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#define INF 2100000000

int n, m;
int t[301];
int map[301][301];

void floyd()
{
	int i, j, k;

	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
			if(map[j][i]!=INF)
			{
				for(k = 0; k < n; k++)
					if(map[j][i]+map[i][k]<map[j][k])
						map[j][k] = map[i][k]+map[j][i];
			}
}

int main()
{
	int i, j, k, l;

	scanf("%d%d",&n,&m);
	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
			map[i][j] = INF;
	for(i = 0; i < m; i++)
	{
		scanf("%d",&k);
		for(j = 0; j < k; j++)
			scanf("%d",&t[j]);
		for(l = 0; l < k; l++)
			for(j = 0; j < k; j++)
				if(l!=j)
					map[t[l]-1][t[j]-1] = map[t[j]-1][t[l]-1] = 1;
	}
	floyd();
	int min = INF;
	for(i = 0; i < n; i++)
	{
		int tmp = 0;
		for(j = 0; j < n; j++)
			if(i!=j&&map[i][j]!=INF)
				tmp += map[i][j];
		if(tmp<min)
			min = tmp;
	}
	printf("%d\n",min*100/(n-1));
	return 0;
}