A6714. 「SDOI2012」走迷宫
编程题
省选/NOI-
知识点
题目描述
Morenan 被困在了一个迷宫里。迷宫可以视为 $n$ 个点 $m$ 条边的有向图，其中 Morenan 处于起点 $s$，迷宫的终点设为 $t$。可惜的是，Morenan 非常的脑小，他只会从一个点出发随机沿着一条从该点出发的有向边，到达另一个点。这样，Morenan 走的步数可能很长，也可能是无限，更可能到不了终点。若到不了终点，则步数视为无穷大。但你必须想方设法求出 Morenan 所走步数的期望值。
输入格式
第一行四个整数，$n,m,s,t$。
接下来 $m$ 行，每行两个整数 $u, v$ ，表示有一条从 $u$ 到 $v$ 的边。
接下来 $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
说明/提示
| 测试点 | $n\leq$ | $m\leq$ |
| :----------: | :----------: | :----------: |
| $1\sim 6$ | $10$ | $100$ |
| $7\sim 12$ | $200$ | $10^4$ |
| $13\sim 20$ | $10^4$ | $10^6$ |
另外，均匀分布着 $40\%$ 的数据，图中没有环，也没有自环。
对于 $100\%$ 的数据，$1\leq n\leq 10^4$，$0\leq m \leq 10^6$，**保证强连通分量的大小不超过** $\boldsymbol{100}$。
| :----------: | :----------: | :----------: |
| $1\sim 6$ | $10$ | $100$ |
| $7\sim 12$ | $200$ | $10^4$ |
| $13\sim 20$ | $10^4$ | $10^6$ |
另外，均匀分布着 $40\%$ 的数据，图中没有环，也没有自环。
对于 $100\%$ 的数据，$1\leq n\leq 10^4$，$0\leq m \leq 10^6$，**保证强连通分量的大小不超过** $\boldsymbol{100}$。