﻿ bzoj 1001: [BeiJing2006]狼抓兔子 最短路+对偶图 - 鸿网互联

# bzoj 1001: [BeiJing2006]狼抓兔子 最短路+对偶图

```const
maxn=2000009;

var
s,t,n,m,e:longint;
last,d,state:array[0..maxn] of longint;
side:array[1..maxn*3] of record
x,y,z,next:longint;
end;
v:array[0..maxn] of boolean;
flag:boolean;

begin
inc(e);
side[e].x:=x; side[e].y:=y; side[e].z:=z;
side[e].next:=last[x]; last[x]:=e;
inc(e);
side[e].x:=y; side[e].y:=x; side[e].z:=z;
side[e].next:=last[y]; last[y]:=e;
end;

procedure init;
var
i,j,ans,x:longint;
begin
ans:=maxlongint;
flag:=true;
if (n=1)or(m=1) then flag:=false;
if (n=1)and(m=1) then
begin
writeln(0);
exit;
end;
if n=1 then
begin
for i:=1 to m-1 do
begin
if x<ans then ans:=x;
end;
writeln(ans);
exit;
end;
if m=1 then
begin
for i:=1 to n-1 do
begin
if x<ans then ans:=x;
end;
writeln(ans);
exit;
end;
s:=0;
t:=2*(n-1)*(m-1)+1;
for i:=1 to m-1 do
begin
end;
for i:=2 to n-1 do
for j:=1 to m-1 do
begin
end;
for i:=1 to m-1 do
begin
end;
for i:=1 to n-1 do
begin
for j:=2 to m-1 do
begin
end;
end;
for i:=1 to n-1 do
for j:=1 to m-1 do
begin
end;
end;

procedure spfa;
var
begin
fillchar(d,sizeof(d),\$7f div 3);
d[s]:=0;
fillchar(v,sizeof(v),true);
v[s]:=false;
tail:=1;
state[1]:=s;
repeat
i:=last[u];
while i>0 do
with side[i] do
begin
if d[x]+z<d[y] then
begin
d[y]:=d[x]+z;
if v[y] then
begin
v[y]:=false;
inc(tail);
if tail>t+7 then tail:=1;
state[tail]:=y;
end;
end;
i:=next;
end;
v[u]:=true;