作者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