首页 > 代码库 > 2953: [Poi2002]商务旅行
2953: [Poi2002]商务旅行
2953: [Poi2002]商务旅行
Time Limit: 3 Sec Memory Limit: 128 MBSubmit: 8 Solved: 8
[Submit][Status]
Description
某首都城市的商人要经常到各城镇去做生意，他们按自己的路线去做，目的是为了更好的节约时间。
假设有N个城镇，首都编号为1，商人从首都出发，其他各城镇之间都有道路连接，任意两个城镇之间如果有直连道路，在他们之间行驶需要花费单位时间。该国公路网络发达，从首都出发能到达任意一个城镇，并且公路网络不会存在环。
你的任务是帮助该商人计算一下他的最短旅行时间。
Input
第一行有一个整数N，1<=n<=30 000，为城镇的数目。下面N-1行，每行由两个整数a 和b (1<=a, b<=n; a<>b)组成，表示城镇a和城镇b有公路连接。在第N+1行为一个整数M，下面的M行，每行有该商人需要顺次经过的各城镇编号。
Output
输出该商人旅行的最短时间。
Sample Input
5
1 2
1 5
3 5
4 5
4
1
3
2
5
1 2
1 5
3 5
4 5
4
1
3
2
5
Sample Output
7
HINT
Source
题解：本来想在codevs做一道线段树题目的，可是进入线段树分类后就发现了这个（HansBug：呵呵呵呵这个也叫线段树我也是醉了 phile：尔等蒟蒻胆敢抢我台词？嗯哼？ HansBug：我错了^_^）只要学过LCA的童鞋不难发现这就是一个最裸的LCA，直接上倍增搞搞就行了，连加上边长数组都免了。。。
1 type 2 point=^node; 3 node=record 4 g:longint; 5 next:point; 6 end; 7 8 var 9 i,j,k,l,m,n,t:longint; 10 a:array[0..50000] of point; 11 c:array[0..20,0..50000] of longint; 12 d:array[0..50000] of longint; 13 function min(x,y:longint):longint;inline; 14 begin 15 if x<y then min:=x else min:=y; 16 end; 17 function max(x,y:longint):longint;inline; 18 begin 19 if x>y then max:=x else max:=y; 20 end; 21 procedure swap(var x,y:longint);inline; 22 var z:longint; 23 begin 24 z:=x;x:=y;y:=z; 25 end; 26 procedure add(x,y:longint);inline; 27 var p:point; 28 begin 29 new(p); 30 p^.g:=y; 31 p^.next:=a[x]; 32 a[x]:=p; 33 end; 34 procedure dfs(x:longint);inline; 35 var p:point; 36 begin 37 p:=a[x]; 38 while p<>nil do 39 begin 40 if c[0,p^.g]=0 then 41 begin 42 c[0,p^.g]:=x; 43 d[p^.g]:=d[x]+1; 44 dfs(p^.g); 45 end; 46 p:=p^.next; 47 end; 48 end; 49 function getfat(x,y:longint):longint;inline; 50 var i,j,k:longint; 51 begin 52 i:=0; 53 while y>0 do 54 begin 55 if odd(y) then x:=c[i,x]; 56 inc(i);y:=y div 2; 57 end; 58 getfat:=x; 59 end; 60 function dis(x,y:longint):longint; 61 var 62 a1,a2,a3,i,j,k,l:longint; 63 begin 64 if d[x]<d[y] then swap(x,y); 65 a1:=x;a2:=y; 66 x:=getfat(x,d[x]-d[y]); 67 if x=y then exit(d[a1]-d[a2]); 68 for i:=20 downto 0 do 69 begin 70 if c[i,x]=0 then continue; 71 if c[i,x]<>c[i,y] then 72 begin 73 x:=c[i,x]; 74 y:=c[i,y]; 75 end 76 end; 77 a3:=c[0,x]; 78 exit(d[a1]+d[a2]-d[a3]-d[a3]); 79 end; 80 81 begin 82 readln(n); 83 for i:=1 to n do a[i]:=nil; 84 for i:=1 to n-1 do 85 begin 86 readln(j,k); 87 add(j,k);add(k,j); 88 end; 89 fillchar(c,sizeof(c),0); 90 fillchar(d,sizeof(d),0); 91 c[0,1]:=-1; 92 dfs(1);c[0,1]:=0; 93 for i:=1 to 20 do 94 for j:=1 to n do 95 c[i,j]:=c[i-1,c[i-1,j]]; 96 readln(m); 97 readln(j);l:=0; 98 for i:=1 to m-1 do 99 begin100 k:=j;101 readln(j);102 t:=dis(k,j);103 l:=l+t;104 end;105 writeln(l);106 readln;107 end.108
2953: [Poi2002]商务旅行
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。