Dijkstra's Algo

即使中間多了一個 Ａ 2.5, 0.4 在下一輪仍然可以 update 成2.9

但如果是更差的結果, seattle: 3 不需要更新

Solution - Dijkstra for 1631

1. create an effort matrix stores effort record

2. create PriorityQueue accept int[] : new_dist(effort), row, col, order by effort (minHeap)

3. while PriorityQueue is not empty

   1. poll node data from PriorityQueue (the smallest dist and row, col index)

   2. if dist > effort[row][col] ⇒ skip this round

   3. if row & col == last cell ⇒ return result

   4. search this node's all neighbors, find new dist ⇒ new smaller effort

   5. if find new dist < effort[new_row][new_col] ⇒ update effort[new_row][new_col] = new dist, and offer new smaller dist into PriorityQueue

https://www.youtube.com/watch?v=FabSLaGu0NI