[問題] ACM 104
看板Prob_Solve (計算數學 Problem Solving)作者chchwy (mat)時間16年前 (2008/11/19 21:59)推噓0(0推 0噓 0→)留言0則, 0人參與討論串1/2 (看更多)
先附上題目
http://online-judge.uva.es/p/v1/104.html
請教各位
我在寫這題的時候，參考了Algorithmist上的解答
http://www.algorithmist.com/index.php/UVa_104
網頁上寫說可以用修改過的 Floyd-Warshall Algo. 來解這題
順便提出了一個新的遞迴公式
d(i,j) = max{ d(i,k)*d(k,j) , d(i,j) } where i!=j
就我的理解，照上面這個公式最後解出來的d(i,j)應該是profit最大
但是題目要求的是：所有profit>1%的路徑中，路徑最短的那條。
請問這是怎麼回事呢?
ps.網頁上好像有稍微提到一下，但不是說得很清楚
ps. 我是為了解這題才去學Floyd-Warshall
初學有理解不清的地方，還請各位多多指教~_~...
--
夜精小德 Char - 巨龍之喉 (前月神殿) PvP
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 203.68.15.209
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
