题意
略。
题解
神仙纳什均衡。
首先，这张图是个有向无环图，大大简化了问题。
为了方便，我们将追捕者叫做A，被追捕者叫做B。
考虑在上面dp，设(f_{x, y, t})为当前在(t)时刻末，且A在点(x)，B在点(y)时的期望得分。（注意，A要最小化这个期望得分，B要最大化这个期望得分）
假设我们已经知道了(t + 1)时刻各种情况的答案，则考虑A和B如何做出最优决策。
做出最优决策，可以从A的角度单方面考虑，理解为A在以概率数组({p_i})对所有转移状态作决策时，B能做出一种相应的决策以最大化得分，而A要做出一个最优决策（对应一个最优的({p_i})），使得B最大化的得分是A能做的所有决策中最小的。
以上也就是纳什均衡的模型。
关于本题的一些简单情形的纳什均衡模型可以看这里提到的。
重要的是把这个纳什均衡模型转化为一个可用数学语言表达的东西。
设(e_{i, j})为A做出第(i)种决策，B做出第(j)种决策的期望得分，并设A有(n)种决策，B有(m)种决策，当前的期望得分为(S)，则
[ ext{minimize} S \
sum_{i = 1} ^ n p_i = 1 \
forall j in [1, m], sum_{i = 1} ^ n p_i e_{i, j} leq S
]
变换一下，(x_i = frac{p_i}{S})，则(S = frac{1}{sum x_i})，有
[ ext{minimize} sum_{i = 1} ^ n x_i \
forall j in [1, m], sum_{i = 1} ^ n x_i e_{i, j} leq 1
]
则用单纯形求解即可。复杂度不关键，关键是跑的很快。
坠痛苦的是单纯形不会打了
#include <bits/stdc++.h>
using namespace std;
typedef double db;
const int N = 45;
const db eps = 1e-8, inf = 1e9;
int n, m, t, sr, sk;
bool vis[N][N][N];
db dp[N][N][N];
vector <int> g[N];
void add (int x, int y) {
g[x].push_back(y);
}
namespace LinearPro {
int n, m, id[N]; db a[N][N];
// id means x_id[i] sits on the position where x_i originally sat
void pivot (int b, int nb) {
swap(id[b + n], id[nb]);
db k = -a[b][nb]; a[b][nb] = -1;
for (int i = 0; i <= n; ++i) {
a[b][i] /= k;
}
for (int i = 0; i <= m; ++i) {
if (a[i][nb] && i != b) {
k = a[i][nb], a[i][nb] = 0;
for (int j = 0; j <= n; ++j) {
a[i][j] += a[b][j] * k;
}
}
}
}
void init () {
for (int i = 1; i <= n + m; ++i) {
id[i] = i;
}
for ( ; ; ) {
int b = 0, nb = 0; double w = -eps;
for (int i = 1; i <= m; ++i) {
if (a[i][0] < w) {
b = i, w = a[i][0];
}
}
if (!b) {
break;
}
for (int i = 1; i <= n; ++i) {
if (a[b][i] > eps) {
nb = i;
break;
}
}
pivot(b, nb);
}
}
db simplex () {
for ( ; ; ) {
int b = 0, nb = 0; double w = eps;
for (int i = 1; i <= n; ++i) {
if (a[0][i] > w) {
nb = i, w = a[0][i];
}
}
if (!nb) {
break;
}
w = inf;
for (int i = 1; i <= m; ++i) {
if (a[i][nb] < -eps) {
if (-a[i][0] / a[i][nb] < w) {
b = i, w = -a[i][0] / a[i][nb];
}
}
}
pivot(b, nb);
}
db ret = 0;
for (int i = 1; i <= m; ++i) {
if (id[n + i] <= n) {
ret += a[i][0];
}
}
return 1.0 / ret;
}
}
db dfs (int x, int y, int z) {
if (vis[x][y][z]) {
return dp[x][y][z];
}
vis[x][y][z] = 1;
if (x == y) {
return dp[x][y][z] = 0;
}
if (z == t) {
return dp[x][y][z] = 1;
}
for (auto i : g[x]) {
for (auto j : g[y]) {
dfs(i, j, z + 1);
}
}
int n = 0, m = 0;
for (auto i : g[x]) {
++n, m = 0;
for (auto j : g[y]) {
LinearPro :: a[++m][n] = dp[i][j][z + 1] + 1;
}
}
for (int j = 1; j <= n; ++j) {
LinearPro :: a[0][j] = -1;
}
for (int i = 1; i <= m; ++i) {
LinearPro :: a[i][0] = -1;
}
LinearPro :: n = n, LinearPro :: m = m;
LinearPro :: init();
dp[x][y][z] = LinearPro :: simplex();
return dp[x][y][z];
}
int main () {
scanf("%d%d%d%d%d", &n, &m, &sr, &sk, &t);
for (int i = 1, x, y; i <= m; ++i) {
scanf("%d%d", &x, &y), add(x, y);
}
for (int i = 1; i <= n; ++i) {
add(i, i);
}
printf("%.3lf
", dfs(sr, sk, 0));
return 0;
}