混沌的城市

混沌的城市

测试数据来自 system/1937

描述

这是一个太阳从西边升起的情人节,木姑娘邀请我一起去逛街。

城市中有n个路口,它们两两之间存在道路。

路口i到路口j之间的道路距离为Aij,保证了Aij=Aji且Aii=0。

紫色的阳光养育着人心罪恶的萌发,城市的道路被以一种随机的方式,形成了树的结构,很多道路没有了,只保留了n-1条道路,却仍然保证了城市的连通性。

但是,木姑娘要逛街,逛街要走最短路径,不是么?

格式

输入格式

第一行一个整数n。下面n行每行n个整数,第i行第j个整数为Aij。
数据保证Aii=0且Aij=Aji对于所有i,j成立。
2<=n<=1000。
-1000<=Aij<=1000。

输出格式

输出n行。每行包含n个实数。第i行第j个整数为i到j的路径的期望长度,答案四舍五入保留到小数点后第四位。
(也就是问,随机得到一棵生成树,然后在这棵树上i到j的距离的期望值是多少。)

样例1

样例输入1

3
0 1 1
1 0 1
1 1 0

样例输出1

0.0000 1.3333 1.3333
1.3333 0.0000 1.3333
1.3333 1.3333 0.0000

限制

对于60%的数据,n<=5。
对于100%的数据,n<=500。

来源

感谢**Sevenkplus**

信息

ID
1948
难度
(无)
分类
a 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
上传者