[理工] 95清大-演算法 15題

看板Grad-ProbAsk作者 (科)時間12年前 (2012/02/08 21:47), 編輯推噓3(3推 0噓 6→)
留言9則, 4人參與, 最新討論串1/1
http://imageshack.us/photo/my-images/716/ssspo.jpg/ 有先爬文 本來想要用directed acyclic graph的解法 先topological sort 再從topological的順序 依序作Relax，這樣可以達到O(V+E) 不過題目沒有說是acyclic QQ 另外題目說cost在1~5 這樣子會影響複雜度嗎？ 有請神人 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.233.31.211 ※ 編輯: zensword 來自: 118.233.31.211 (02/08 21:48)
推
02/08 22:08, , 1F
直覺是想到counting sort啦....
02/08 22:08, 1F
推
02/08 22:14, , 2F
樓上正解 開個 5|V| 的陣列替代heap
02/08 22:14, 2F
→
02/08 22:18, , 3F
哦哦 原來如此 陷在priority queue才想不到 感謝樓上兩位
02/08 22:18, 3F
→
02/08 22:21, , 4F
!@#$ 想通了 原本在想怎麼改Prim orz
02/08 22:21, 4F
→
02/08 22:32, , 5F
真的！豁然開朗
02/08 22:32, 5F
→
02/08 22:37, , 6F
orz 其實我後來想的是Kruskal 現在才了解二樓的意思
02/08 22:37, 6F
→
02/08 22:58, , 7F
Dijkstra的extract min讓我只往priority queue思考QQ
02/08 22:58, 7F
推
02/09 12:39, , 8F
用bellman-ford呢?
02/09 12:39, 8F
→
02/09 12:50, , 9F
嗚 我記錯了 沒事QQ
02/09 12:50, 9F
‣ 更多 zensword 的文章
文章代碼(AID): #1FCdq0vf (Grad-ProbAsk)