HDOJ 1869

 1 #include<stdio.h>
 2 int a[101][101];
 3 #define inf 0xffffff;
 4 void floyed(int n)
 5 {
 6     int i,j,k;
 7     for(k=0;k<n;k++)
 8     {
 9         for(i=0;i<n;i++)
10         {
11             for(j=0;j<n;j++)
12             {
13                 if(a[i][k]+a[k][j]<a[i][j])
14                     a[i][j]=a[j][i]=a[i][k]+a[k][j];
15             }
16         }
17     }
18 }
19 int main()
20 {
21     int n,m,i,j,x,y,flag;
22     while(scanf("%d %d",&n,&m)!=EOF)
23     {
24         flag=1;
25         for(i=0;i<n;i++)
26             for(j=0;j<n;j++)
27                 a[i][j]=inf;
28         for(i=0;i<m;i++)
29             scanf("%d %d",&x,&y),
30             a[x][y]=a[y][x]=1;
31         floyed(n);
32         for(i=0;i<n;i++)
33         {
34             for(j=i+1;j<n;j++)
35             {
36                 if(a[i][j]>7)
37                 {
38                     flag=0;
39                     break;
40                 }
41             }
42         }
43         if(flag)
44             printf("Yes
");
45         else
46             printf("No
");
47     }
48 }

View Code

floyed算法，转化为图论中的顶点对之间的距离，不能超过7.

9885303

2013-12-23 23:14:55

Accepted

1869

62MS

292K

683 B

C++

泽泽