noi05-聪聪和可可

这题还是比较容易的，不过第一次时写挂了。。。主要思路就是类似spfa的方法预处理得到next数组，然后就是记忆化搜索，我没用链式邻接表，但既然数组模拟没Mle，那就不该了吧。。
贴代码（这个是我最近写的最短的代码了）：

const
     maxn=1010;
var
   g,dist,next:array[1..maxn,0..maxn] of longint;
   vis:array[1..maxn] of boolean;
   q:array[0..maxn] of longint;
   f:array[1..maxn,1..maxn] of double;
   N,E,C,M:longint;
procedure init;
var
   i,a,b:longint;
begin
     readln(N,E);
     readln(C,M);
     for i:=1 to N do g[i,0]:=0;
     for i:=1 to E do begin
         readln(a,b);
         inc(g[a,0]); g[a,g[a,0]]:=b;
         inc(g[b,0]); g[b,g[b,0]]:=a;
     end;
     fillchar(f,sizeof(f),0);
end;
procedure path;
var
   top,last,i,j,now:longint;
begin
     for i:=1 to N do
     for j:=1 to N do dist[i,j]:=maxlongint;
     for i:=1 to N do begin
         dist[i,i]:=0;
         next[i,i]:=i;
         fillchar(vis,sizeof(vis),false);
         vis[i]:=true;
         top:=0; last:=1; q[last]:=i;
         while top<last do begin
               inc(top);
               now:=q[top];
               vis[now]:=false;
               for j:=1 to g[now,0] do
                   if (dist[i,now]+1<dist[i,g[now,j]])or((dist[i,now]+1=dist[i,g[now,j]])and(now<next[g[now,j],i])) then begin
                      dist[i,g[now,j]]:=dist[i,now]+1;
                      next[g[now,j],i]:=now;
                      if not vis[g[now,j]] then begin
                         inc(last);
                         q[last]:=g[now,j];
                         vis[g[now,j]]:=true;
                      end;
                   end;
         end;
     end;
end;
function getf(p,q:longint):double;
var
   sum:double;
   i:longint;
begin
     if p=q then exit(0);
     p:=next[p,q]; if p=q then exit(1);
     p:=next[p,q]; if p=q then exit(1);
     if f[p,q]>1e-9 then exit(f[p,q]);
     sum:=getf(p,q);
     for i:=1 to g[q,0] do
         sum:=sum+getf(p,g[q,i]);
     sum:=sum/(g[q,0]+1)+1;
     getf:=sum;
     f[p,q]:=sum;
end;
procedure main;
begin
     assign(input,'cchkk.in');
     assign(output,'cchkk.out');
     reset(input);
     rewrite(output);
     init;
     path;
     write(getf(C,M):0:3);
     close(input);
     close(output);
end;
begin
     main;
end.