傳送門

身為紫題這道題算是挺水的了，就一個bfs求出兩點最短路徑，然后bfs程序中順便求出 n x t [ c ] [ g ] nxt[c][g] nxt[c][g] 陣列（表示聰聰在 c c c 位置，可可在 g g g 位置聰聰下一步會走到哪個點上），

狀態的話基本是個人都能想到： f [ c ] [ g ] f[c][g] f[c][g] 表示聰聰在 c c c 位置，可可在 g g g 位置平均情況下聰聰還要多少步才能吃到可可，

方程： f [ c ] [ g ] = ( ∑ i ∈ s o n s f [ n x t [ n x t [ c ] [ g ] ] [ g ] ] [ i ] ) + 1 + f [ [ n x t [ c ] [ g ] ] [ g ] ] [ g ] ) ) ÷ ( ∣ s o n s ∣ + 1 ) f[c][g] = (\sum \limits_{i\in sons} f[nxt[nxt[c][g]][g]][i]) + 1 + f[[nxt[c][g]][g]][g]))\div (\vert sons \vert + 1) f[c][g]=(i∈sons∑?f[nxt[nxt[c][g]][g]][i])+1+f[[nxt[c][g]][g]][g]))÷(∣sons∣+1)

接下來隨便搞一搞就好了，

C o d e : Code: Code:

#include <cstdio>
#include <queue>
#include <cstring>

#define reg register

int n, m, st, en, Dis[1001][1001], nxt[1001][1001], head[1001], tot;
double f[1001][1001];
struct Edge {
	int to, nxt;
} e[2005];

inline void AddEdge(int u, int v) {
	e[++ tot].to = v, e[tot].nxt = head[u], head[u] = tot;
	e[++ tot].to = u, e[tot].nxt = head[v], head[v] = tot;
}

inline void bfs(int root) {
	bool vis[1001] = {};
	std::queue<int> q;
	vis[root] = true;
	q.push(root);
	while (q.size()) {
		int u(q.front()); q.pop();
		for (reg int i(head[u]); i; i = e[i].nxt) {
			reg int v(e[i].to);
			if (!vis[v] || (Dis[root][u] < Dis[root][v] && u < nxt[v][root])) {
				Dis[root][v] = Dis[root][u] + 1, nxt[v][root] = u;
				if (!vis[v])
					q.push(v), vis[v] = true;
			}
		}
	}
}

inline void scan() {
	int u, v;
	scanf("%d%d%d%d", &n, &m, &st, &en);
	for (reg int i(1); i <= m; ++ i)
	scanf("%d%d", &u, &v), AddEdge(u, v);
	for (reg int i(1); i <= n; ++ i)
	for (reg int j(1); j <= n; ++ j) f[i][j] = -1;
}

inline double dfs(int c, int g) {
	if (f[c][g] != -1) return f[c][g];
	if (Dis[c][g] == 0) return f[c][g] = 0.0;
	if (Dis[c][g] <= 2) return f[c][g] = 1.0;
	int C(nxt[nxt[c][g]][g]), P(0);
	f[c][g] = 0;
	for (reg int i(head[g]); i; i = e[i].nxt)
	++ P, f[c][g] += dfs(C, e[i].to) + 1;
	f[c][g] += dfs(C, g) + 1;
	f[c][g] /= P + 1;
	return f[c][g];
}

int main() {
	scan();
	for (reg int i(1); i <= n; ++ i) bfs(i);
	dfs(st, en);
	printf("%.3lf", f[st][en]);
}