HDOJ 1869 六度分开

HDOJ 1869 六度分离

就是两两之间的路径不超过7.因为隔六个人，就是七条边，用Floyd。

代码：

#include<iostream>
using namespace std;
int n,dist[105][105];
void Floyd()
{
     int i,j,k,temp;
     for( k=0; k<n; k++)
      for( i=0; i<n; i++)
       for( j=0; j<n; j++){
        if( dist[i][k]&&dist[j][k]){
            temp=dist[i][k]+dist[k][j];
            if( dist[i][j]==0)
                dist[i][j]=temp;
            if( dist[i][j]>temp)
                dist[i][j]=temp;
        }
       }
}
int main()
{
    int m,a,b,i,j;
    bool flag;
    while( scanf("%d%d",&n,&m)!=EOF){
           memset(dist,0,sizeof(dist));
           while( m--){
                  scanf("%d%d",&a,&b);
                  dist[a][b]=dist[b][a]=1;
           }
           Floyd();
           flag=true;
           for( i=0; i<n; i++){
                for( j=0; j<n; j++){
                     if( i!=j){
                         if( dist[i][j]==0||dist[i][j]>7){
                             flag=false;
                             break;
                         }
                     }
                }
           }
           if( flag)
               printf("Yes\n");
           else
               printf("No\n");
    }
    return 0;
}