Morenan被困在了一个迷宫里。迷宫可以视为N个点M条边的有向图,其中Morenan处于起点S,迷宫的终点设为T。可惜的是,Morenan非常的脑小,他只会从一个点出发随机沿着一条从该点出发的有向边,到达另一个点。这样,Morenan走的步数可能很长,也可能是无限,更可能到不了终点。若到不了终点,则步数视为无穷大。但你必须想方设法求出Morenan所走步数的期望值。
F.A.Qs | Home | ProblemSet | Status | Ranklist | Contest | Login | Register | 捐赠本站 |
---|
测试点
|
N
|
M
|
Hint
|
[1, 6]
|
<=10
|
<=100
|
|
[7, 12]
|
<=200
|
<=10000
|
|
[13, 20]
|
<=10000
|
<=1000000
|
保证强连通分量的大小不超过100
|