[東方S3]铃仙•优昙华院•稻叶

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 reisen.in 输出文件 reisen.out

Problem 2

铃仙优昙华院稻叶(reisen.cpp/c/pas)

题目描述

  在幻想乡,铃仙优昙华院稻叶(レイセン・うどんげいん・イナバ)是从月球逃到永远亭的月兔。同样居住在永远亭的地球兔子因幡帝老是对铃仙恶作剧。某一天,铃仙终于决定要惩罚一下帝,不过首先得在迷途竹林里把帝抓住。永远亭的迷途竹林可以视为一个由N个路口(编号1..N)M条单向路连接的区域。开始时,帝在路口1,每一个单位时间,帝会以相同的概率走到相邻的路口或是停留在当前路口,一条路可以重复走,但是帝不会走回头路,也就是说如果帝从路口x走到了路口y,在到过其他路口前,她一定不会从路口y走回路口x。现在铃仙想知道,在T秒钟以后,在哪个路口抓到帝的可能性最大。

输入格式

  第1行:3个非负整数N, M, T

  第2..M+1行:每行2个整数u,v,表示存在一条从路口u到路口v的单向路

输出格式

  第1..N行:一个实数,第i行表示在路口i抓到帝的概率,单位为%,保留3位小数

输入样例

3 4 2

1 2

1 3

2 1

2 3

输出样例

11.111

27.778

61.111

样例解释

  时刻0: 1(100%)

  时刻1: 1(33.333%) 2(33.333%) 3(33.333%)

  时刻2: 1(11.111%) 2(11.111%+16.667%) 3(33.333%+11.111%+16.667%)

  在时刻2时,只能从路口2走向路口3,不可返回路口1

  若时刻2选择停留在路口2,时刻3时仍然不可以从路口2走回路口1,因为尚未走到过其他路口。

数据范围

  对于30%的数据,N ≤ 5, M ≤ 10, T ≤ 10

  对于60%的数据,N ≤ 10, M ≤ 50, T ≤ 500

  对于100%的数据,N ≤ 50, M ≤ 2000, T ≤ 500

注意

  输入数据中无重复的边,且不存在自环。