← 返回题目
题库练习 「SDOI2012」走迷宫
← 上一题 下一题 →

A6714 | 「SDOI2012」走迷宫

时间限制1s
内存限制512MB
通过 / 提交0/0

题目描述

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

输入格式

第一行四个整数，$n,m,s,t$。

接下来 $m$ 行，每行两个整数 $u, v$ ，表示有一条从 $u$ 到 $v$ 的边。

输出格式

一个浮点数，保留小数点后 $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
C++ 编辑器
输入
输出