板上沒找到解答 就自己寫了一個 希望可以拋磚引玉 想問板上大神們有沒有想到時間複雜度更低的解法呢？
題目如下：
https://i.imgur.com/ncMbVkF.jpg
參考解答：
https://i.imgur.com/sHvMN1T.jpg

如果用min heap, find-min可以降到O(1), build可以降到O(n)不過我是用nxn matrix, min另存, 這樣每次更新需檢查2n-1個entry

1.建好n^2個f(x,y) -> O(n^2)2.用這n^2個元素建立heap -> O(n^2)3.m次操作 會更動m*(2n-1)個decrease-key -> O(mnlgn)

我nxn沒有建heap, 只有存matrix, 每次改值只在更動到的(2n-1)個entry找最小和目前的min比, 我自己推是O(mn), 還是哪裡想錯了呢QQ

matrix一開始用完就丟進heap裡了 要改都在heap改

所以我沒有要建heap...只是2d array

C大 m次更動中有可能改到最小的元素 這樣要怎麼找min？

對...那應該還是要用n個heap才對，感謝!

我是寫建立min-heap欸，這樣找min都是O(1),n個就O(n),insert/delete也是O(nlgn)

我的想法是先建出nxn的元素然後放進Fibonacci heap O(n^2)更改一次decrease-key O(2n-1)共m次O(mn)total（n^2+mn)這樣想不知道有沒有錯

感謝各位大大！a大用Fibonacci Heap時間複雜度沒錯。 原本我卡的點是在做decrease key之前要先search這個element ，會是O(n)，所以才轉而可慮用AVL。不過後來想到可以用hashmap 來記錄各個點的在heap中index 位置，這樣Fibonacci 的decrease key就可以amortize O(1)整體time complexity 就會是O(n^2)m更新的話就會是O(mn)

喔喔 Fibonacci heap時間當然快(？