#P6030. [SDOI2012] 走迷宫

[SDOI2012] 走迷宫

题目描述

Morenan 被困在了一个迷宫里。迷宫可以视为 nn 个点 mm 条边的有向图,其中 Morenan 处于起点 ss,迷宫的终点设为 tt。可惜的是,Morenan 非常的脑小,他只会从一个点出发随机沿着一条从该点出发的有向边,到达另一个点。这样,Morenan 走的步数可能很长,也可能是无限,更可能到不了终点。若到不了终点,则步数视为无穷大。但你必须想方设法求出 Morenan 所走步数的期望值。

输入格式

第一行四个整数,n,m,s,tn,m,s,t

接下来 mm 行,每行两个整数 u,vu, v ,表示有一条从 uuvv 的边。

输出格式

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

6 6 1 6
1 2
1 3
2 4
3 5
4 6
5 6
3.000
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
9.500
2 0 1 2
INF

提示

测试点 nn\leq mm\leq
161\sim 6 1010 100100
7127\sim 12 200200 10410^4
132013\sim 20 10410^4 10610^6

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

对于 100%100\% 的数据,1n1041\leq n\leq 10^40m1060\leq m \leq 10^6保证强连通分量的大小不超过 100\boldsymbol{100}