混沌的城市

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

描述

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

城市中有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**

情人节邀请赛之木姐姐的情人节梦录[Marathon]

未参加
状态
已结束
规则
OI
题目
20
开始于
2015-02-13 12:00
结束于
2015-02-15 12:00
持续时间
48.0 小时
主持人
参赛人数
273