logo AlgoBeat OnlineJudge
登录 注册

#102707. [BZOJ 2707] [SDOI2012]走迷宫

内存限制:128 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

输入格式

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

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

输出格式

一个浮点数,保留小数点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

Hint

[1, 6]

<=10

<=100

[7, 12]

<=200

<=10000

[13, 20]

<=10000

<=1000000

保证强连通分量的大小不超过100

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

样例

样例输入

样例输出