3361: [Usaco2004 Jan]培根距离

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 16  Solved: 13

[][][]

Description

    贝茜和其他奶牛联系是通过一连串的中间奶牛传递的，所以当第一头牛和贝茜联系，第二头牛和第一头牛联系，第三头牛和第二头牛联系，…一贝茜就能依次联系到其中的每一头奶牛． 联系长度是指传递过程中涉及的奶牛的数目（不包括贝茜）．任何一头奶牛（不包括贝茜）的培根距离是指从贝茜到该奶牛的最小联系长度．最小的培根距离是1（当贝茜能够直接与该奶牛联系时）.约输有C头牛，编号1到C，贝茜是1号．有P(1≤P≤10000)组奶牛相互联系．请找到最大的培根距离．

Input

    第1行：C和P.

    第2到P+1行：每行两头牛，它们之间有联系．

Output

 

    输出最大培根距离．

Sample Input

6 7

1 2

2 3

2 4

3 4

3 5

4 5

6 5

Sample Output

4

样例说明

从贝茜到6奶牛的距离是4．联系路径(2，4，5，6)和(2，3，5，6)都适合

HINT

 

Source

 

题解：spfa模板题，水水哒

在这个里面加入了一个新的优化方法，昨天在wnjxyk的空间里面看到的（OTLwnjxyk），在spfa入队前，可以在队列内的值进行判重操作，这样子可以提高速度，而且必要时可以起到压缩队列所用空间的作用，可以将队列有效长度控制在N以内，这样子必要时只需要开一个循环队列即可解决空间问题，GET！！！（OTLwnjxyk）

1 type 2         point=^node; 3         node=record 4                 g,w:longint; 5                 next:point; 6         end; 7 var 8         i,j,k,l,m,n,f,r:longint; 9         p:point;10         a:array[0..100000] of point;11         b,c:array[0..100000] of longint;12         d:array[0..1000000] of longint;13 procedure add(x,y,z:longint);inline;14         var p:point;15         begin16                 new(p);p^.g:=y;p^.w:=z;17                 p^.next:=a[x];a[x]:=p;18         end;19 begin20         readln(n,m);21         for i:=1 to n do a[i]:=nil;22         for i:=1 to m do23                 begin24                         readln(j,k);25                         add(j,k,1);add(k,j,1);26                 end;27         fillchar(b,sizeof(b),0);28         fillchar(c,sizeof(c),0);29         fillchar(d,sizeof(d),0);30         f:=1;r:=2;31         d[1]:=1;c[1]:=1;b[1]:=1;32         while f
      
       nil do36                                 begin37                                         if ((b[p^.g]=0) or ((b[p^.g]=1) and (b[p^.g]>(b[d[f]]+p^.w)))) and (c[p^.g]=0) then38                                                 begin39                                                         b[p^.g]:=b[d[f]]+p^.w;40                                                         c[p^.g]:=1;41                                                         d[r]:=p^.g;42                                                         inc(r);43                                                 end;44                                         p:=p^.next;45                                 end;46                         c[d[f]]:=0;47                         inc(f);48                 end;49         for i:=1 to n do dec(b[i]);50         l:=0;51         for i:=1 to n do if b[i]>l then l:=b[i];52         writeln(l);53 end.