#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int num_dot,num_side,iq[110],weight[110],dis[110][110];
void init()
{
int i,t1,t2;
memset(dis,127,sizeof(dis));
for(i=0;i<num_side;i++)
{
scanf("%d%d",&t1,&t2);
dis[t1][t2]=1;
dis[t2][t1]=1;
}
}
void spfa(int st)
{
int x,i;
queue<int>qq;
memset(iq,0,sizeof(iq));
memset(weight,127,sizeof(weight));
iq[st]=1;
qq.push(st);
weight[st]=0;
while(qq.size())
{
x=qq.front();
qq.pop();
iq[x]=0;
for(i=0;i<num_dot;i++)
if(weight[i]>weight[x]+dis[x][i])
{
weight[i]=weight[x]+dis[x][i];
if(!iq[i])
{
qq.push(i);
iq[i]=1;
}
}
}
}
bool isright()
{
int i,j;
for(i=0;i<num_dot;i++)
{
spfa(i);
for(j=i+1;j<num_dot;j++)
if(weight[j]>7)
return 0;
}
return 1;
}
int main()
{
while(scanf("%d%d",&num_dot,&num_side)!=EOF)
{init();
if(isright())
printf("Yes\n");
else
printf("No\n");}
}hdu1869六度分离，spfa实现求最短路,布布扣,bubuko.com
原文：http://blog.csdn.net/stl112514/article/details/37603293