TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4571
  • 题目
  • P4571【CERC2017】旅游指南
    限制 : 时间限制 : 20000 MS   空间限制 : 565536 KB  SPJ
    评测说明 : 1s,512m
    问题描述

    给定一张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}时视为正确。

    样例输入 1

    5 8
    1 2
    1 3
    1 4
    2 3
    2 4
    3 5
    5 4
    2 5

    样例输出 1

    4.1111111111

    样例输入 2

    4 4
    1 2
    1 3
    2 4
    3 4

    样例输出 2

    3.0000000000


    来源  bzoj 5197