网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[東方S3]铃仙•优昙华院•稻叶
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23: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 |
注意 |
输入数据中无重复的边,且不存在自环。 |