作者chchwy (mat)
看板Prob_Solve
標題Re: [問題] ACM 104
時間Mon Dec 1 22:31:03 2008
關於這題
我後來在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