[理工] 108交大資演 9

看板Grad-ProbAsk作者 (粒粒)時間5年前 (2020/01/28 23:39), 5年前編輯推噓3(308)
留言11則, 4人參與, 5年前最新討論串1/1
https://i.imgur.com/P8JGuQP.jpg
請問一下有人會這題嗎QQ 追好久還是寫錯 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.12.133.75 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1580225960.A.3DA.html

01/28 23:54, 5年前 , 1F
用臨接矩陣做Dijkstra's
01/28 23:54, 1F

01/29 00:15, 5年前 , 2F
題目要問什麼
01/29 00:15, 2F
※ 編輯: leegaga61029 (101.12.133.75 臺灣), 01/29/2020 01:14:46

01/29 09:55, 5年前 , 3F
這一題trace的時候其實就是先從priority queue找最小,
01/29 09:55, 3F

01/29 09:55, 5年前 , 4F
然後再判斷哪些需要decrease key,不過如果沒有想到這個
01/29 09:55, 4F

01/29 09:55, 5年前 , 5F
直接追蹤也可以
01/29 09:55, 5F

01/29 09:56, 5年前 , 6F
題目我記得是問u_max最後的值
01/29 09:56, 6F

01/29 15:38, 5年前 , 7F

01/29 15:39, 5年前 , 8F
剛剛做的供參字醜抱歉
01/29 15:39, 8F

01/29 22:09, 5年前 , 9F
這題就是Dijkstra啊 只是他沒用priority queue來存
01/29 22:09, 9F

01/29 22:10, 5年前 , 10F
目前距離最小的點而已
01/29 22:10, 10F

01/29 22:12, 5年前 , 11F
他在找當前最小點的時候 花了O(V)來找而已
01/29 22:12, 11F
文章代碼(AID): #1UC5MeFQ (Grad-ProbAsk)