bzoj#P4055. [Ctsc2015] misc

[Ctsc2015] misc

题目描述

小强和 B 君是好朋友,小强除了 B 君还有很多好朋友,比如洁妹。

B 君除了小强也还有很多好朋友,比如 R 君。

他们还有很多共同的好朋友,比如小花,葱娘和其他 33 个人。

B 君发现,人与人之间的关系可以看成是一个无向图,每个人看成一个点,人与人之间的关系看成一条边。

不同的人在社会中的号召力不一样,我们用 aia_i 来表示第 ii 个人的号召力。

人与人之间的关系也各不相同,可能非常友好,可能只是泛泛之交;可能天天腻在一起,可能一年才联系一次。

为此,我们用长度边权 bjb_j 来刻画第 jj 条边对应的两个用户的亲密程度,长度约小,双方就越亲密。

同时,我们用宽度边权 cjc_j 来刻画第 jj 条边对应的两个用户的交流频率,宽度越大,两个人沟通的频率也就越高。

一条路径的长度指的是这条路径上的所有边的长度边权之和,一条路径的宽度指的是这条路径上的所有边的宽度边权的乘积。

当两个人 sstt 想要交流的时候,他们会选择长度最短的路径来交流。由于最短路可能有多个,我们称 sstt 的最短路的宽度为 σst\text{σst},是所有 sstt 的长度最短的路径的宽度和。

同时,我们用 σst(v)\text{σst(v)} 表示所有从 sstt,且经过 vv 的长度最短的路径的宽度和,即 vvs,ts,t 的影响力。

一个人 vv 在图中的传播力 R(v)\text{R(v)} 可以被定义为如下函数:

即对图中所有不包含 vv 的点对,分别计算 vv 对该点对的影响力除以该点对的最短路的宽度,再乘上这个点对中两个点的号召力,最后将所有点对的计算结果加和得到节点在图中的传播力。

B 君想快速知道所有节点在图中的传播力。

当他去问小强的时候,小强说:“我有一个绝妙的做法,可惜题面太短,写不下。”

你知道怎么做吗?

输入格式

第一行包含 22 个正整数 n,mn,m,分别表示图的点数和边数。

接下来 nn 行中的第 ii 行有 11 个非负整数 aia_i,表示第 ii 个人的号召力。  接下来 mm 行中的第 jj 行有 33 个整数 xj,yj,bjx_j,y_j,b_j 和一个实数 cjc_j,表示点 xjx_j 和点 yjy_j 之间有一条长度边权为 bjb_j,宽度边权为 cjc_j的边。

输出格式

nn 行,每行一个实数 R(i)\text{R(i)},表示第 ii 个点在图中的传播力,误差在 10610^{-6} 内。

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

数据规模与约定

对于测试点 141 \sim 41n1001 \le n \le 100

对于测试点 575 \sim 7,所有 bj=1b_j = 1

对于测试点 9129 \sim 12m=n1m = n-1

对于奇数测试点,所有 ai=1a_i=1

对于偶数测试点,所有 cj=1c_j=1

对于全部测试点,1n,m10001\le n,m \le 10000<aj2550 < a_j \le 2550<bj150 < b_j \le 150.5cj20.5 \le c_j \le 2cjc_j 的小数部分最多 1212 位,保证图连通。