bzoj#P4055. [Ctsc2015] misc
[Ctsc2015] misc
题目描述
小强和 B 君是好朋友,小强除了 B 君还有很多好朋友,比如洁妹。
B 君除了小强也还有很多好朋友,比如 R 君。
他们还有很多共同的好朋友,比如小花,葱娘和其他 个人。
B 君发现,人与人之间的关系可以看成是一个无向图,每个人看成一个点,人与人之间的关系看成一条边。
不同的人在社会中的号召力不一样,我们用 来表示第 个人的号召力。
人与人之间的关系也各不相同,可能非常友好,可能只是泛泛之交;可能天天腻在一起,可能一年才联系一次。
为此,我们用长度边权 来刻画第 条边对应的两个用户的亲密程度,长度约小,双方就越亲密。
同时,我们用宽度边权 来刻画第 条边对应的两个用户的交流频率,宽度越大,两个人沟通的频率也就越高。
一条路径的长度指的是这条路径上的所有边的长度边权之和,一条路径的宽度指的是这条路径上的所有边的宽度边权的乘积。
当两个人 和 想要交流的时候,他们会选择长度最短的路径来交流。由于最短路可能有多个,我们称 到 的最短路的宽度为 ,是所有 到 的长度最短的路径的宽度和。
同时,我们用 表示所有从 到 ,且经过 的长度最短的路径的宽度和,即 对 的影响力。
一个人 在图中的传播力 可以被定义为如下函数:
即对图中所有不包含 的点对,分别计算 对该点对的影响力除以该点对的最短路的宽度,再乘上这个点对中两个点的号召力,最后将所有点对的计算结果加和得到节点在图中的传播力。
B 君想快速知道所有节点在图中的传播力。
当他去问小强的时候,小强说:“我有一个绝妙的做法,可惜题面太短,写不下。”
你知道怎么做吗?
输入格式
第一行包含 个正整数 ,分别表示图的点数和边数。
接下来 行中的第 行有 个非负整数 ,表示第 个人的号召力。 接下来 行中的第 行有 个整数 和一个实数 ,表示点 和点 之间有一条长度边权为 ,宽度边权为 的边。
输出格式
共 行,每行一个实数 ,表示第 个点在图中的传播力,误差在 内。
5 5
1 2 3 4 5
1 2 2 0.7
3 4 2 0.9
1 3 1 1.1
2 4 1 1.3
4 5 10 2
4.762887
8.621053
9.378947
67.237113
0.000000
数据规模与约定
对于测试点 ,。
对于测试点 ,所有 。
对于测试点 , 。
对于奇数测试点,所有 。
对于偶数测试点,所有 。
对于全部测试点,,,,, 的小数部分最多 位,保证图连通。