HDU 1869 六度分离【floyd】

题意：给出n个人，m个关系，问是否满足任意两个人之间的距离通过6个人就可以连接

用floyd就可以了，注意距离是大于7

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring> 
 4 #include <cmath> 
 5 #include<stack>
 6 #include<vector>
 7 #include<map> 
 8 #include<set>
 9 #include<queue> 
10 #include<algorithm>  
11 using namespace std;
12 
13 typedef long long LL;
14 const int INF = (1<<30)-1;
15 const int mod=1000000007;
16 const int maxn=505;
17 int d[maxn][maxn];
18 int n,m; 
19 
20 int floyd(){
21     for(int k=0;k<n;k++)
22      for(int i=0;i<n;i++)
23       for(int j=0;j<n;j++)
24       d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
25       
26       for(int i=0;i<n;i++){
27           for(int j=0;j<n;j++){
28               if(d[i][j]>7) return 0;
29           }
30       }
31       return 1;
32 }
33 
34 int main(){
35     while(scanf("%d %d",&n,&m)!=EOF){
36         for(int i=0;i<n;i++){
37             for(int j=0;j<n;j++){
38                 if(i==j) d[i][j]=0;
39                 else d[i][j]=INF;
40             }
41         }
42         for(int i=1;i<=m;i++){
43             int u,v;
44             scanf("%d %d",&u,&v);
45             d[u][v]=d[v][u]=1;
46         }
47         
48         if(floyd()) printf("Yes
");
49         else printf("No
");
50     }
51     return 0;
52 }

View Code