TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3853
  • 题目
  • P3853constandine
    限制 : 时间限制 : - MS   空间限制 : 165536 KB
    评测说明 : 2s
    问题描述

    古月族是一个神奇的种族,有一天古月腾和古月豪在一起看《地狱神探(constandine)》。

         剧中,小康是一个驱魔师。有一天,他找到了一本驱魔指南,上面记录了许多咒语,每个咒语由许多字符组成,例如:“!?####T_Tabc”。

    仪式一开始,需要呼告,咒语总是从某个字符串st开始,最后总是以某个字符串en结束。咒语之间存在着一种古老的联系,如念完咒语i后,接着只能念k条规定的咒语(保证从任何一个咒语开始念都能念到en,并且从st开始,能念到任何咒语,后面的咒语不能念到前面的,即不能倒着念),否则会破坏自然的平衡,反噬自身,变成恶魔。每两个咒语连着念会产生一定的魔法值Wij。

    念到一句咒语时(还没念到到en),会面临k种选择来完成整个仪式,并且每种选择的概率为1/k。

    小康为了提前准备仪式,以防走火入魔,他想让你帮帮他,算出整个咒语的魔法值的期望值是多少?

    四舍五入,保留两位小数。

    输入格式

    第一行为两个正整数n,m,表示有n条咒语(保证字符串长度不超过5),有m种联系。

    第二行到第m+1行,每行两个字符串,一个正整数,a,b,c,代表咒语a与咒语b有联系,且连续念产生的魔法值为c(输入出现的第一个不同的字符串为st,k==0的字符串为en)。

    输出格式

    输出整个咒语的魔法值的期望值,四舍五入保留两位小数。

    样例输入

    4 4
    ah aaaaa 1
    ah hjh 2
    aaaaa hjh 3
    hjh ht 4

    样例输出

    7.00

    提示

    【数据范围】

        对于20%的数据,n<=100

        对于另20%的数据,n<=1000

        对于另20%的数据,n<=10000

        对于100%的数据,n<=100000,m<=2*n