作者netsphere (再一次重来...)
看板Prob_Solve
标题Re: [问题] Floyd演算法的一个题目
时间Wed Jul 30 22:30:55 2008
: 如图:http://www.badongo.com/pic/4102668
有点懒的算~ 叫程式帮你算吧
http://rafb.net/p/zgvUbv26.html
其实我也有个问题要问 >///<
递回式: distk(i,j)=Min(distk-1(i,j),distk-1(i, k)+distk-1(k, j))
直接用递回式定义来写是 O(n^4) 我的程式就是.....
为什麽可以压到O(n^3) 是那里偷吃步了?
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.165.198.173
1F：推 s0908744:不好意思 那个...程式..不会RUN. 07/30 22:44
2F：→ netsphere:五楼交给你了 07/30 22:49
3F：→ LPH66:最外层的t就是中介点 所以不必再一层u 正确性由DP保证 07/30 22:51
4F：推 scan33scan33:1F去下载devC run吧！google一下就可以找到用法了 07/31 01:56
5F：→ scan33scan33:正确性简单的induction on t得证 07/31 01:58
6F：→ scan33scan33:on k说错，然後证明的这个方向就跟程式写法一样。 07/31 01:58
7F：→ scan33scan33:就很自然!?(偷偷当五楼XD) 07/31 01:59