思路：这个题看着感觉不能dp，其实是可以dp的，因为狼每次走两步，兔子每次走一步，每进行一轮以后，狼和兔子的距离
肯定是在接近的，没有相同的状态，dp之前预处理出来，每一步狼该往哪里走。
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define pii pair<int, int>using namespace std;const int N = + ;
const int M = 1e5 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 +;int n, m, S, T, dis[N][N], nx[N][N];
bool vis[N];
vector<int> edge[N];double f[N][N];void bfs(int s) { memset(vis, false, sizeof(vis));
dis[s][s] = ; vis[s] = true;
queue<int> que;
for(int i = ; i < edge[s].size(); i++) {
int v = edge[s][i];
dis[s][v] = ;
nx[s][v] = v;
vis[v] = true;
que.push(v);
} while(!que.empty()) {
int u = que.front(); que.pop();
for(int i = ; i < edge[u].size(); i++) {
int v = edge[u][i];
if(!vis[v]) {
dis[s][v] = dis[s][u] + ;
nx[s][v] = nx[s][u];
vis[v] = true;
que.push(v);
} else if(vis[v] && dis[s][u] + == dis[s][v]) {
nx[s][v] = min(nx[s][v], nx[s][u]);
}
}
}
}double dp(int i, int j) {
if(f[i][j] >= ) return f[i][j];
if(i == j) return f[i][j] = ;
if(nx[i][j] == j || nx[nx[i][j]][j] == j) return f[i][j] = ; f[i][j] = ;
int nxi = nx[nx[i][j]][j];
double p = 1.0 / ((int) edge[j].size() + ); for(int k = ; k < edge[j].size(); k++) {
f[i][j] += p * dp(nxi, edge[j][k]);
} f[i][j] += p * dp(nxi, j);
return f[i][j];
}int main() { scanf("%d%d", &n, &m);
scanf("%d%d", &S, &T); for(int i = ; i <= n; i++)
for(int j = ; j <= n; j++)
f[i][j] = -; for(int i = ; i <= m; i++) {
int u, v; scanf("%d%d", &u, &v);
edge[u].push_back(v);
edge[v].push_back(u);
} for(int i = ; i <= n; i++) bfs(i); printf("%.3f\n", dp(S, T));
return ;
}/*
*/
