pku2139.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 77 行

#include <stdio.h>

int main()
{
	int i, j, k, N, M, n, min;
	int mb[1000];
	int dis[301][301];
	
	scanf("%d%d", &N, &M);
	
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
		{
			dis[i][j] = 1000;	
		}	
	}
	
	while (M--)
	{
		scanf("%d", &n);
		for (i = 0; i < n; i++)
		{
			scanf("%d", &mb[i]);	
		}
		for (i = 0; i < n; i++)
		{
			for (j = 0; j < n; j++)
			{
				if (i == j) continue;
				dis[mb[i]-1][mb[j]-1] = 1;	
			}
		}	
	}
	
	for (i = 0; i < N; i++)
	{
		dis[i][i] = 0;	
	}
	
	for (k = 0; k < N; k++)
	{
		for (j = 0; j < N; j++)
		{
			for (i = 0; i < N; i++)
			{
				if (dis[i][j] > dis[i][k] + dis[j][k])
				{
					dis[i][j] = dis[i][k] + dis[j][k];	
					dis[j][i] = dis[i][k] + dis[j][k];	
				}	
			}	
		}	
	}

	for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
		{
			if (i == j) continue;
			dis[i][i] += dis[i][j];	
		}	
	}
	
	min = dis[0][0];
	for (i = 1; i < N; i++)
	{
		if (dis[i][i] < min)
		{
			min = dis[i][i];	
		}	
	}
	printf("%d\n", min * 100 / ( N - 1));
	return 0;
}