OpenJudge

1039:敌不过想念

总时间限制:
10000ms
单个测试点时间限制:
1000ms
内存限制:
512000kB
描述

Zhonghaoxi 和 MoonTear 双双去了帝都读大学,可惜他们不在一所学校,所以他们对
对方朝思暮想。周末,他们决定骑自行车去帝都郊外旅游。
可是帝都是一个神奇的城市,郊外有很多收费站,分别编号为 1~n。经过一次第 i 个收
费站就要交 ci大洋作为买路钱。收费站之间有 m 条公路,而且还是单行道,当然这些公路
是不收钱的。(不然就太黑了是吧)
现在 Zhonghaoxi 和 MoonTear 在第 1 号收费站,他们想去第 n 号收费站。(当然 1
号和 n 号收费站也是要收费的啦)他们选择路线的方式比较奇怪。
首先,他们当然想花费最少的钱。
另外,他们也比较随性,所以如果他们在第 i 号收费站,那么他们会等概率地去一个能
够符合上一个条件且从当前收费站能到达的收费站。
磨子桥技工学校的 yzjc 教授知道这件事情之后,很好奇每个收费站收到钱的期望是多
少。
(提示:收到钱的期望=价钱×经过这个收费站的概率)


输入
第一行两个正整数 n, m。
第二行 n 个正整数 ci。
接下来 m 行每行两个正整数 u, v,表示有一条从 u 到 v 的单行道。
输出
输出 n 行,每行一个实数,表示第 i 号收费站收到钱的期望,保留三位小数。
样例输入
5 6
1 1 1 1000 1
1 2
1 3
1 4
2 5
3 5
4 5
样例输出
1.000
0.500
0.500
0.000
1.000
提示
对于 40%的数据,1 ≤ n ≤ 10, 1 ≤ m ≤ 30。
对于 70%的数据,1 ≤ n ≤ 300, 1 ≤ m ≤ 1000。
对于 100%的数据,1 ≤ n ≤ 50,000, 1 ≤ m ≤ 200,000。
对于 100%的数据,1 ≤ ci ≤ 10,000, 1 ≤ u, v ≤ n。
对于 100%的数据,保证没有自环,保证可以从 1 号收费站到达 n 号收费站。
(精度有误差的点已删除)
来源
hejiaao

yjq naive

全局题号
7697
添加于
2014-12-05
提交次数
15
尝试人数
7
通过人数
6