A7566 | $[ABC144F] Fork in the Road$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

有 $N$ 个房间和 $M$ 条只能单向通行的通道组成的洞窟。每个房间编号为 $1$ 到 $N$。 高桥君现在在房间 $1$，房间 $N$ 是出口。第 $i$ 条通道连接房间 $s_i$ 和房间 $t_i$（$s_i < t_i$），只能从房间 $s_i$ 走向房间 $t_i$。已知除了房间 $N$ 以外，每个房间至少有一条出发的通道。 高桥君尝试从洞窟中逃脱。每当他到达一个房间时（开始时视为到达房间 $1$），他会等概率随机选择一条从该房间出发的通道前进。 高桥君的朋友青木君可以在高桥君从房间 $1$ 出发前，选择封锁一条通道（也可以什么都不做）。但不能封锁导致高桥君无法到达房间 $N$ 的通道。 设高桥君到达房间 $N$ 前经过的通道数的期望为 $E$。请你求出青木君在使 $E$ 最小化的情况下，$E$ 的值。

输入通过标准输入给出，格式如下： > $N$ $M$ > $s_1$ $t_1$ > $s_2$ $t_2$ > $\vdots$ > $s_M$ $t_M$

输出青木君在使 $E$ 最小化的情况下，$E$ 的值。 当你的输出与标准答案的绝对误差或相对误差不超过 $10^{-6}$ 时，将被判定为正确。

输入 #1

输出 #1

1.5000000000

输入 #2

3 2
1 2
2 3

输出 #2

2.0000000000

输入 #3

输出 #3

3.0133333333

C++ 编辑器

输入

输出