3361: [Usaco2004 Jan]培根距离
3361: [Usaco2004 Jan]培根距离
HansBug
发布于 2018-04-10 17:16:55
发布于 2018-04-10 17:16:55
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 begin
16 new(p);p^.g:=y;p^.w:=z;
17 p^.next:=a[x];a[x]:=p;
18 end;
19 begin
20 readln(n,m);
21 for i:=1 to n do a[i]:=nil;
22 for i:=1 to m do
23 begin
24 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<r do
33 begin
34 p:=a[d[f]];
35 while p<>nil do
36 begin
37 if ((b[p^.g]=0) or ((b[p^.g]=1) and (b[p^.g]>(b[d[f]]+p^.w)))) and (c[p^.g]=0) then
38 begin
39 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.本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015-04-05 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录