比较简单的数学期望,先预处理出当聪聪在i,可可在j时聪聪往哪个点走
然后做dp即可,我用了记忆化搜索实现
type node=record
po,next:longint;
end; var d,pos:array[..,..] of longint;
f:array[..,..] of double;
v:array[..] of boolean;
e:array[..] of node;
c,p,q:array[..] of longint;
len,s,t,i,j,n,m,x,y:longint; procedure add(x,y:longint);
begin
inc(len);
e[len].po:=y;
e[len].next:=p[x];
p[x]:=len;
end; procedure bfs(s:longint);
var f,r,i,x,y:longint;
begin
d[s,s]:=;
fillchar(v,sizeof(v),false);
v[s]:=true;
f:=;
r:=;
i:=p[s];
while i<> do
begin
y:=e[i].po;
v[y]:=true;
inc(r);
q[r]:=y;
d[s,y]:=;
pos[s,y]:=y;
i:=e[i].next;
end;
while f<=r do
begin
x:=q[f];
i:=p[x];
while i<> do
begin
y:=e[i].po;
if not v[y] then
begin
d[s,y]:=d[s,x]+;
pos[s,y]:=pos[s,x];
v[y]:=true;
inc(r);
q[r]:=y;
end
else if (d[s,y]=d[s,x]+) and (pos[s,x]<pos[s,y]) then
pos[s,y]:=pos[s,x]; i:=e[i].next;
end;
inc(f);
end;
end; function dfs(x,y:longint):double;
var i,w:longint;
begin
if x=y then exit();
if (pos[x,y]=y) or (pos[pos[x,y],y]=y) then exit();
if f[x,y]<>- then exit(f[x,y]);
i:=p[y];
f[x,y]:=dfs(pos[pos[x,y],y],y);
while i<> do
begin
w:=e[i].po;
f[x,y]:=f[x,y]+dfs(pos[pos[x,y],y],w);
i:=e[i].next;
end;
f[x,y]:=f[x,y]/(c[y]+)+;
exit(f[x,y]);
end; begin
readln(n,m);
readln(s,t);
for i:= to m do
begin
readln(x,y);
add(x,y);
add(y,x);
inc(c[x]);
inc(c[y]);
end;
for i:= to n do
begin
for j:= to n do
f[i,j]:=-;
pos[i,i]:=i;
f[i,i]:=;
bfs(i);
end;
writeln(dfs(s,t)::);
end.