hdu1869 六度分离（Floyd）

8 7
0 1
1 2
2 3
3 4
4 5
5 6
6 7
8 8
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 0

Yes
Yes

#include <cstdio>
#include <cstring>
#define INF 99999999
#define M 217
int n , m ,a ,b ,x;
int dis[M][M];
int min(int a,int b)
{
	int m;
	m = a < b ? a : b;
	return m;
}
void Floyd()
{
	for(int k = 0; k < n ; k++ )
	{
		for(int i = 0; i < n ; i++ )
		{
			for(int j = 0; j < n ; j++ )
			{
				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
			}
		}
	}
}

void init()
{
	for(int i = 0; i < n ; i++ )
	{
		for(int j = 0; j < n ; j++ )
		{
			if( i == j )
				dis[i][j] = 0 ;//这一步必须归为零
			else
				dis[i][j]=INF;
		}
	}
}
int main()
{
	int i, j;
	int cont[M];
	while(~scanf("%d%d",&n,&m))
	{
		init();
		memset(cont,0,sizeof(cont));
		for( i = 0; i < m; i++ )
		{
			scanf("%d%d",&a,&b);
			dis[a][b] = dis[b][a] = 1;
		}
		
		Floyd();
		
		int flag = 0;
		for(i = 0; i < n; i++)
		{
			for(j = 0; j < n; j++)
			{
				if(dis[i][j] > 7)
				{
					flag = 1;
					break;
				}
			}
		}
		if(flag)
			printf("No\n");
		else
			printf("Yes\n");
	}
	return 0;
}