仙人掌上的最短路，这里有详细的题解
http://pan.baidu.com/s/1wzCpC
我觉得讲的很清楚，不懂的见代码注释吧
1 type node=record 2 po,next,num:longint; 3 end; 4 5 var e,w:array[0..200010] of node; 6 dfn,low,p,q,mark,s,d,dis,dep,fa:array[0..10010] of longint; 7 anc:array[0..10010,0..20] of longint; 8 v:array[0..10010] of boolean; 9 st:array[0..1000010] of longint; 10 t,h,i,len,x,y,z,n,m,tot,qq:longint; 11 12 function min(a,b:longint):longint; 13 begin 14 if a>b then exit(b) else exit(a); 15 end; 16 17 procedure add(x,y,z:longint); 18 begin 19 inc(len); 20 e[len].po:=y; 21 e[len].next:=p[x]; 22 e[len].num:=z; 23 p[x]:=len; 24 end; 25 26 procedure fadd(x,y:longint); 27 begin 28 inc(len); 29 w[len].po:=y; 30 w[len].next:=q[x]; 31 q[x]:=len; 32 end; 33 34 procedure spfa; 35 var f,r,i,x,y:longint; 36 begin 37 f:=1; 38 r:=1; 39 st[1]:=1; 40 for i:=2 to n do //d[]表示根节点到其他节点的最短路 41 d[i]:=2000000007; 42 while f<=r do 43 begin 44 x:=st[f]; 45 i:=p[x]; 46 v[x]:=false; 47 while i<>0 do 48 begin 49 y:=e[i].po; 50 if d[y]>d[x]+e[i].num then 51 begin 52 d[y]:=d[x]+e[i].num; 53 if not v[y] then 54 begin 55 inc(r); 56 st[r]:=y; 57 v[y]:=true; 58 end; 59 end; 60 i:=e[i].next; 61 end; 62 inc(f); 63 end; 64 end; 65 66 procedure get(x,y:longint); 67 begin 68 inc(tot); 69 while y<>x do 70 begin 71 mark[y]:=tot; //环上节点（除最高点）标为同一颜色 72 fadd(x,y); //建“杨天”树 73 y:=fa[y]; 74 end; 75 end; 76 77 procedure dfs1(x:longint); 78 var i,y:longint; 79 begin 80 inc(h); 81 dfn[x]:=h; 82 low[x]:=h; 83 i:=p[x]; 84 while i<>0 do 85 begin 86 y:=e[i].po; 87 if fa[x]<>y then 88 begin 89 if dfn[y]=0 then 90 begin 91 fa[y]:=x; 92 dis[y]:=dis[x]+e[i].num; //dis[]表示得到的dfs树上根节点到节点的距离 93 dfs1(y); 94 end; 95 low[x]:=min(low[x],low[y]); 96 if low[y]>dfn[x] then 97 fadd(x,y); //dfs树的树边 98 end; 99 i:=e[i].next; 100 end; 101 i:=p[x]; 102 while i<>0 do 103 begin 104 y:=e[i].po; 105 if (dfn[y]>dfn[x]) and (fa[y]<>x) then 106 begin 107 get(x,y); //处理环 108 s[tot]:=dis[y]-dis[x]+e[i].num; //求这个环的长度 109 end; 110 i:=e[i].next; 111 end; 112 end; 113 114 procedure dfs2(x:longint); 115 var i,y:longint; 116 begin 117 for i:=1 to t do 118 begin 119 y:=anc[x,i-1]; 120 if y<>0 then anc[x,i]:=anc[y,i-1] else break; 121 end; 122 i:=q[x]; 123 while i<>0 do 124 begin 125 y:=w[i].po; 126 fa[y]:=x; 127 anc[y,0]:=x; 128 dep[y]:=dep[x]+1; //在杨天树上的深度 129 dfs2(y); 130 i:=w[i].next; 131 end; 132 end; 133 134 function lca(x,y:longint):longint; 135 var i,p,a,b,z:longint; 136 begin 137 if x=y then exit(0); //注意 138 if dep[x]<dep[y] then 139 begin 140 p:=x; x:=y; y:=p; 141 end; 142 a:=x; 143 b:=y; 144 p:=trunc(ln(dep[x])/ln(2)); 145 if dep[a]>dep[b] then 146 begin 147 for i:=p downto 0 do 148 if dep[a]-1 shl i>=dep[b] then a:=anc[a,i]; 149 end; 150 if a=b then exit(d[x]-d[a]); //如果点a是点x的祖先那么a,x之间最短距离为d[x]-d[a] 151 for i:=p downto 0 do 152 if (anc[a,i]<>anc[b,i]) then 153 begin 154 a:=anc[a,i]; 155 b:=anc[b,i]; 156 end; 157 z:=fa[a]; 158 if (mark[a]<>0) and (mark[a]=mark[b]) then //最后提到环上两点要讨论 159 begin 160 p:=abs(dis[a]-dis[b]); 161 exit(d[x]-d[a]+d[y]-d[b]+min(p,s[mark[a]]-p)); 162 end 163 else exit(d[x]+d[y]-2*d[z]); //否则直接当树做 164 end; 165 166 begin 167 readln(n,m,qq); 168 for i:=1 to m do 169 begin 170 readln(x,y,z); 171 add(x,y,z); 172 add(y,x,z); 173 end; 174 t:=trunc(ln(n)/ln(2)); 175 spfa; 176 len:=0; 177 dfs1(1); 178 dfs2(1); 179 for i:=1 to qq do 180 begin 181 readln(x,y); 182 writeln(lca(x,y)); 183 end; 184 end.