板上没找到解答 就自己写了一个 希望可以抛砖引玉 想问板上大神们有没有想到时间复杂度更低的解法呢？
题目如下：
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时间当然快(？