<div class="post_brief"><p>
最近很颓啊。</p>

 

这题很久之前看过。当时以为是高消就没管。然后开坑之神idy做了之后仔细一想才知道不是。

 

这题的做法是dp。首先因为边数少所以不用floyd，直接bfs预处理出所有t[i][j]表狼在i，兔子在j的时候狼下一步去哪。然后有一个结论是每一步两个玩意的距离至少缩短1，所以状态是不会有环的，这也是为啥可以不用高消。然后坑点是不能直接开状态队列，因为那不是拓补序。要先把每个点的入度算出来再跑dp。结局是我的代码超长。

 

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;


struct edge {
int t;
edge *next;
};


#define mkword(x,y) (((x)<<16)|(y))
#define hiword(x) ((x)>>16)
#define loword(x) ((x)&0x0000ffff)


const int maxn = 1009;
const int maxst = 1000009;
const int inf = 0x3f3f3f3f;


int n, m, st, te, deg[maxn], d[maxn], t[maxn][maxn], ind[maxn][maxn];
edge elst[maxn << 1], *ep(elst), *head[maxn];
double f[maxn][maxn], g[maxn][maxn], c[maxn], ans;


inline void addEdge(int u, int v) {
ep-> t = v;
ep-> next = head[u];
head[u] = ep ++;
}


void bfs(int p0) {
static int q[maxn];
int hd(0), tl(1);
memset(d, -1, sizeof(d));
d[q[0] = p0] = 0;
while (hd < tl) {
int p(q[hd ++]);
for (edge* e = head[p]; e; e = e-> next)
if (d[e-> t] == -1) {
d[e-> t] = d[p] + 1;
q[tl ++] = e-> t;
}
}
for (int p = 1; p <= n; ++ p)
if (p == p0) {
t[p][p] = p;
}
else {
t[p][p0] = inf;
for (edge* e = head[p]; e; e = e-> next)
if (d[p] == d[e-> t] + 1 && e-> t < t[p][p0])
t[p][p0] = e-> t;
}
}


void dp() {
static int q[maxst];
static bool iq[maxn][maxn];
int hd(0), tl(1);
memset(iq, 0, sizeof(iq));
memset(f, 0, sizeof(f));
memset(g, 0, sizeof(g));
memset(ind, 0, sizeof(ind));
ans = 0;
q[0] = mkword(st, te);
iq[st][te] = 1;
while (hd < tl) {
int i(hiword(q[hd])), j(loword(q[hd])), i0, j0;
++ hd;
if (t[t[i][j]][j] != j) {
for (edge* e = head[j]; e; e = e-> next) {
i0 = t[t[i][j]][j];
j0 = e-> t;
++ ind[i0][j0];
int zn(mkword(i0, j0));
if (!iq[i0][j0]) {
q[tl ++] = zn;
iq[i0][j0] = 1;
}
}
i0 = t[t[i][j]][j];
j0 = j;
++ ind[i0][j0];
int zn(mkword(i0, j0));
if (!iq[i0][j0]) {
q[tl ++] = zn;
iq[i0][j0] = 1;
}
}
}
memset(f, 0, sizeof(f));
memset(g, 0, sizeof(g));
g[st][te] = 1;
ans = 0;
q[0] = mkword(st, te);
hd = 0;
tl = 1;
while (hd < tl) {
int i(hiword(q[hd])), j(loword(q[hd])), i0, j0;
++ hd;
if (i == j) {
ans += f[i][j];
}
else if (t[t[i][j]][j] == j) {
ans += f[i][j] + g[i][j];
}
else {
for (edge* e = head[j]; e; e = e-> next) {
i0 = t[t[i][j]][j];
j0 = e-> t;
g[i0][j0] += g[i][j] * c[j];
f[i0][j0] += (f[i][j] + g[i][j]) * c[j];
int zn(mkword(i0, j0));
– ind[i0][j0];
if (!ind[i0][j0])
q[tl ++] = zn;
}
i0 = t[t[i][j]][j];
j0 = j;
g[i0][j0] += g[i][j] * c[j];
f[i0][j0] += (f[i][j] + g[i][j]) * c[j];
int zn(mkword(i0, j0));
– ind[i0][j0];
if (!ind[i0][j0])
q[tl ++] = zn;
}
}
}


int main() {
#ifndef ONLINE_JUDGE
freopen(“in.txt”, “r”, stdin);
#endif


scanf("%d%d%d%d", &amp;n, &amp;m, &amp;st, &amp;te);
memset(d, 0x3f, sizeof(d));
memset(deg, 0, sizeof(deg));
for (int i = 0; i &lt; m; ++ i) {
	int u, v;
	scanf("%d%d", &amp;u, &amp;v);
	addEdge(u, v);
	addEdge(v, u);
	++ deg[u];
	++ deg[v];
}
for (int i = 1; i &lt;= n; ++ i) {
	bfs(i);
	c[i] = 1.0 / (deg[i] + 1);
}
dp();
printf("%.3lf\n", ans);



}