[TYVJ] P1423 GF和猫咪的玩具

 1 #include<stdio.h>
 2 #include<string.h>
 3 int i,j,n,m,k,x,y,mx,a[110][110];
 4 
 5 int 
 6 pre(void)
 7 {
 8     memset(a,1,sizeof(a));
 9     return 0;
10 }
11 
12 int 
13 add(int x,int y)
14 {
15     a[x][y]=1;
16     a[y][x]=1;
17     return 0;
18 }
19 
20 int
21 min(int a,int b)
22 {
23     if (a<b) return(a);
24     else return(b);
25 }
26 
27 int 
28 init(void)
29 {
30     scanf("%d%d\n",&n,&m);  
31     for(i=1;i<=m;i++)
32     {
33         scanf("%d%d",&x,&y);
34         add(x,y);
35     }
36     return 0;
37 }
38 
39 int 
40 main(void)
41 {
42     pre();
43     init();
44     
45 for(k=1;k<=n;k++)
46     for(i=1;i<=n;i++)
47         for(j=1;j<=n;j++)
48             if ((i!=j)&&(i!=k)&&(k!=j))
49             a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
50     
51     mx=-35111111;
52     for(i=1;i<=n;i++)
53         for(j=1;j<=n;j++)
54         if(i!=j)
55         if (a[i][j]>mx) mx=a[i][j];
56     
57    printf("%d\n",mx);
58     return 0;
59 }
60         
61