推 holik0123:只求S到T應該用DIJKSTRA就行了吧 03/18 23:04
→ holik0123:要DP就用BELL MAN的樣子 03/18 23:05
→ woncho:說的也是，因為看書上用F法從A^0直接跳A^9想說是否有速解~ 03/18 23:12
→ woncho:謝謝囉:) 03/18 23:12
http://ppt.cc/44g4
本題利用Floyd's algorithm
0 9
但矩陣要從A 算到A
一個一個看眼睛都花了，最後還算錯..
它是上三角矩陣，下三角型都是∞，如下：
S A B C D E F G T
┌ ┐
S│ 0 4 3 5 3 ∞ ∞ ∞ ∞│
A│∞ 0 ∞ ∞ ∞ 10 6 ∞ ∞│
B│∞ ∞ 0 ∞ ∞ ∞ 9 5 ∞│
C│∞ ∞ ∞ 0 ∞ 11 ∞ ∞ ∞│
D│∞ ∞ ∞ ∞ 0 ∞ ∞ 2 ∞│
E│∞ ∞ ∞ ∞ ∞ 0 ∞ ∞ 4│
F│∞ ∞ ∞ ∞ ∞ ∞ 0 ∞ 5│
G│∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 1│
T│∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0│
└ ┘
請問有沒有比較快速的解法呢？感謝!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.160.180.229