BZPRO
#5197. [CERC2017]Gambling Guide
内存限制：512 MiB
时间限制：20 Sec
提交
提交记录
讨论
题目描述
给定一张n个点，m条双向边的无向图。
你要从1号点走到n号点。当你位于x点时，你需要花1元钱，等概率随机地买到与x相邻的一个点的票，只有通过票才能走到其它点。
每当完成一次交易时，你可以选择直接使用那张票，也可以选择扔掉那张票然后再花1元钱随机买另一张票。注意你可以无限次扔票。
请使用最佳的策略，使得期望花的钱数最少。
输入格式
第一行包含两个正整数n,m(1<=n,m<=300000)，表示点数和边数。
接下来m行，每行两个正整数u,v(1<=u,v<=n)，表示一条双向边。
输入数据保证无重边、无自环，且1号点一定可以走到n号点。
输出格式
输出一行一个实数，即最少的期望花费，当绝对或者相对误差不超过10^{-6}时视为正确。
样例
样例输入
5 8
1 2
1 3
1 4
2 3
2 4
3 5
5 4
2 5
样例输出
4.1111111111
数据范围与提示
BZPRO