F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 2707. -- [SDOI2012]走迷宫

2707: [SDOI2012]走迷宫

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 1172  Solved: 441
[Submit][Status][Discuss]

Description

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

Input

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

Output

一个浮点数,保留小数点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%的数据,图中没有环,也没有自环

Sample Input

Sample Output

HINT

Source

round 1 day1

[Submit][Status][Discuss]

HOME Back