题意：给你一个有向图， 并指定起点和终点。
问要从起点走向终点， 再从终点走向起点， 最少需要走过多少不同的节点。
对于 100%的数据， 有 N<=100， M<=min(1000,N*N)。 图中可能有重边或者自环
思路：
const oo=;
var head1,head2,vet1,vet2,next1,next2:array[..]of longint;
q:array[..]of record
x,y:longint;
end;
dis,f:array[..,..]of longint;
inq:array[..,..]of boolean;
n,m,i,j,k,cas,tot1,tot2,x,y,z:longint; function min(x,y:longint):longint;
begin
if x<y then exit(x);
exit(y);
end; procedure spfa;
var i,j,u1,u2,e1,e2,v1,v2,t,w,t1,w1,tmp:longint;
begin
for i:= to n do
for j:= to n do
begin
inq[i,j]:=false;
dis[i,j]:=oo;
end;
t:=; w:=; t1:=; w1:=;
q[].x:=; q[].y:=; inq[,]:=true; dis[,]:=;
while t<w do
begin
inc(t); inc(t1);
if t1=(n*n)<< then t1:=;
u1:=q[t1].x; u2:=q[t1].y; inq[u1,u2]:=false; e1:=head1[u1];
while e1<> do
begin
v1:=vet1[e1];
tmp:=dis[u1,u2];
if v1<>u2 then inc(tmp);
if tmp<dis[v1,u2] then
begin
dis[v1,u2]:=tmp;
if not inq[v1,u2] then
begin
inc(w); inc(w1);
if w1=(n*n)<< then w1:=;
q[w1].x:=v1; q[w1].y:=u2; inq[v1,u2]:=true;
end;
end;
e1:=next1[e1];
end; e2:=head2[u2];
while e2<> do
begin
v2:=vet2[e2];
tmp:=dis[u1,u2];
if v2<>u1 then inc(tmp);
if tmp<dis[u1,v2] then
begin
dis[u1,v2]:=tmp;
if not inq[u1,v2] then
begin
inc(w); inc(w1);
if w1=(n*n)<< then w1:=;
q[w1].x:=u1; q[w1].y:=v2; inq[u1,v2]:=true;
end;
end;
e2:=next2[e2];
end; if (u1<>u2)and(dis[u1,u2]+f[u1,u2]-<dis[u2,u1]) then
begin
dis[u2,u1]:=dis[u1,u2]+f[u1,u2]-;
if not inq[u2,u1] then
begin
inc(w); inc(w1);
if w1=(n*n)<< then w1:=;
q[w1].x:=u2; q[w1].y:=u1; inq[u2,u1]:=true;
end;
end;
end;
end; procedure add1(a,b:longint);
begin
inc(tot1);
next1[tot1]:=head1[a];
vet1[tot1]:=b;
head1[a]:=tot1;
end; procedure add2(a,b:longint);
begin
inc(tot2);
next2[tot2]:=head2[a];
vet2[tot2]:=b;
head2[a]:=tot2;
end; begin
assign(input,'uva1057.in'); reset(input);
assign(output,'uva1057.out'); rewrite(output);
while not eof do
begin
read(n,m);
if n= then break;
for i:= to n do
begin
head1[i]:=;
head2[i]:=;
end;
tot1:=; tot2:=;
inc(cas);
writeln('Network ',cas);
for i:= to n do
for j:= to n do
if i<>j then f[i,j]:=oo;
for i:= to m do
begin
read(x,y);
f[x,y]:=;
add1(x,y);
add2(y,x);
end;
for i:= to n do
for j:= to n do
for k:= to n do f[j,k]:=min(f[j,k],f[j,i]+f[i,k]);
if (f[,]=oo)or(f[,]=oo) then
begin
writeln('Impossible');
writeln;
continue;
end;
spfa;
writeln('Minimum number of nodes = ',dis[,]);
writeln;
end;
close(input);
close(output);
end.