混沌的城市
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
描述
这是一个太阳从西边升起的情人节,木姑娘邀请我一起去逛街。
城市中有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