Re: [問題] ACM 104
看板Prob_Solve (計算數學 Problem Solving)作者chchwy (mat)時間16年前 (2008/12/01 22:31)推噓0(0推 0噓 0→)留言0則, 0人參與討論串2/2 (看更多)
關於這題
我後來在uva論壇上找到了相當詳盡的講解
關於Modified Floyd-Warshall
http://online-judge.uva.es/board/viewtopic.php?t=7292
請有興趣的人自行前往:D
※ 引述《chchwy (mat)》之銘言：
: 先附上題目
: 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
: 初學有理解不清的地方，還請各位多多指教~_~...
--
懷著一顆對這個家有無限關愛的心，我 再度流浪到遠方。 --<舒伯特>
這些年來，我唱著歌，唱出愛，可是它對我來說卻是痛苦；
我唱出痛苦，可是它對我來說又是愛。 愛與痛苦就這樣分割著我。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 203.68.15.209
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
