QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 128 MB Total points: 100

# 4138. 走迷宫

统计

Morenan 被困在了一个迷宫里。迷宫可以视为 $N$ 个点 $M$ 条边的有向图,其中 Morenan 处于起点 $S$,迷宫的终点设为 $T$。

可惜的是,Morenan 非常的脑小,他只会从一个点出发随机沿着一条从该点出发的有向边,到达另一个点。这样,Morenan走的步数可能很长,也可能是无限,更可能到不了终点。若到不了终点,则步数视为无穷大。但你必须想方设法求出 Morenan 所走步数的期望值。

输入格式

第 $1$ 行 $4$ 个整数,$N,M,S,T$。

第 $[2, M+1]$ 行每行两个整数 $o_1, o_2$,表示有一条从 $o_14 到 $o_2$ 的边。

输出格式

一个浮点数,保留小数点 $3$ 位,为步数的期望值。若期望值为无穷大,则输出 INF

样例数据

样例 1 输入

6 6 1 6
1 2
1 3
2 4
3 5
4 6
5 6

样例 1 输出

3.000

样例 2 输入

9 12 1 9
1 2
2 3
3 1
3 4
3 7
4 5
5 6
6 4
6 7
7 8
8 9
9 7

样例 2 输出

9.500

样例 3 输入

2 0 1 2

样例 3 输出

INF

子任务

测试点 $N$ $M$ Constraints
$1 \sim 2$ $\leq 10$ $\leq 10$ $ $
$3 \sim 6$ $\leq 12$ $\leq 20$ $ $
$7 \sim 8$ $\leq 200$ $\leq 1\,000$ $ $
$9 \sim 12$ $\leq 200$ $\leq 10\,000$ $ $
$13 \sim 20$ $\leq 10\,000$ $\leq 1\,000\,000$ 保证强连通分量的大小不超过 $100$

另外,均匀分布着 $40\%$ 的数据,图中没有环,也没有自环。